|
|
|
||
Last update: G_I (05.06.2002)
|
|
||
Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)
Demuth O., Kryl R., Kučera A.: Teorie algoritmů I,II. SPN, 1984, 1989
Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987
Odifreddi P.: Classical recursion theory. North-Holland, 1989 |
|
||
Last update: ()
Turingovy stroje, částečně rekurzivní funkce (resp. další matematická upřesnění intuitivního pojmu algoritmu), myšlenka důkazu jejich ekvivalence.
Primitivně rekurzivní funkce.
Pojem univerzální funkce, Kleeneho věta o normální formě a její význam. s-m-n věta.
Rekurzivní a rekurzivně spočetné množiny. Základní vlastnosti. Postova věta. Problém zastavení Turingova stroje a další algoritmicky nerozhodnutelné problémy.
Věta o rekurzi a její aplikace. Riceova věta.
Různé charakterizace rekurzivně spočetných a rekurzivních množin. Věty o jejich generování.
Produktivní a kreativní množiny. Prosté množiny.
Dvojice množin, efektivní neoddělitelnost dvojic množin a Gödelovy věty o neúplnosti.
Relativní vyčíslitelnost, T-převeditelnost.
Operace skoku, její význam jako relativizovaného halting problému a její základní vlastnosti.
Věta o limitní vyčíslitelnosti.
Aritmetická hierarchie. Věta o hierarchii, souvislost s operací skoku. |