FI:I046 Vyčíslitelnost II - Informace o předmětu

I046 Vyčíslitelnost II

Fakulta informatiky
jaro 2000

Rozsah

2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

prof. RNDr. Luboš Brim, CSc. (přednášející)

Garance

Předpoklady

I997 Státní zkouška || ( I007 Vyčíslitelnost && M006 Teorie množin && P998 Souborná zkouška )

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

Osnova

Věta o rekurzi. Zobecněná Riceova věta, injektivní smn-věta, Rogersova věta o isomorfismu, aplikace věty o rekurzi.
Aplikace v logice. Aritmetické množiny a funkce, Goedelova-Rosserova věta o neúplnosti, druhá Goedelova věta o neúplnosti.
Relativizovaná teorie vyčíslitelnosti. Programy s orákulem.
Kleeneho hierarchie. T-redukce, aritmetická hierarchie, tt-redukovatelnost.
Postův problém.
Analytická hierarchie, aplikace v logice.
Vyčíslitelnost nespočetných množin. Úplné částečně uspořádané množiny, domény.

Literatura

Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info

Informace učitele

http://www.fi.muni.cz/usr/brim/I046

Další komentáře

Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.

Předmět je zařazen také v obdobích léto 1998, jaro 1999.