Teória vypočítateľnosti

Pozor skuska !!!
Terminy skusok su vypisane v harkoch na Katedre informatiky.
Je nutne sa na skusku zapisat.

• Sylaby na skusku

Kurz z vypočítateľnosti je ponúkaný v dvoch paralelných prednáškach: jednu prednáša RNDr. Chladný (Teória vypočítateľnosti), druhú Ing. Komara (Teória vypočítateľnosti pre programátorov).

Spoločné rámcové sylaby pre obe verzie prednášok

Funkcie a čiastočné funkcie, projekcie, skladanie funkcií, trojice číslovacích (párovacích) funkcií. Univerzálne funkcie a čiastočné funkcie. Primitívne rekurzívne, rekurzívne funkcie a čiastočne rekurzívne (vypočitateľné) funkcie (na množine N). Primitívne rekurzívne, rekurzívne a rekurzívne spočítateľné množiny a predikáty a ich vlastnosti. Modely vypočítateľnosti (Turingove stroje a iné modely). Ekvivalentnosť modelov vypočítateľnosti. Churchova téza. Problém zastavenia a iné nerozhodnuteľné problémy. Kódovanie nečíselných oborov (oborov slov) do prirodzených čísel.

!!! Táto stránka obsahuje informácie k prednáške, ktorú prednáša RNDr. Chladný.
(Teória vypočítateľnosti) !!!

Prednášajúci: RNDr. M. Chladný (M-249)
E-mail: chladny@dcs.fmph.uniba.sk
Rozsah výuky: 2/2 S
Čas a miesto konania prednášky: Štvrtok 8:10, akvárium II
Čas a miesto konania cvičení: Štvrtok 11:30, akvárium II

Ciele predmetu

Hlavným cieľom predmetu je formalizavať pojmy algoritmickej riešiteľnosti problémov a vypočítateľnosti funkcií a uviesť aplikácie takýchto formalizmov v informatike, logike apod. Pôjde pritom o štandardný klasický výklad pojmov teórie vypočítateľnosti, ktorý bude vedený formou teoretickej prednášky doplnenej teoretickými cvičeniami.

Prednáška je logicky rozčlenená do troch častí. Prvá časť prednášky bude vykladať pojmy teórie vypočítateľnosti nezávisle od konkrétneho výpočtového modelu, v druhej sa budeme zaoberať výpočtovými modelmi, a to registrovými a Turingovými strojmi. Ide teda o modely teoretické, pri ktorých sa často používa abstrakcia potenciálnej uskutočniteľnosti, t.j. tieto modely nebudeme programovať na skutočných počítačoch. Tretia časť prednášky sa bude zaoberať aplikáciami teórie vypočítateľnosti, najmä problematikou (čiastočnej) (ne)rozhodnuteľnosti problémov, ktoré prirodzene vznikajú vrámci informatiky, logiky, resp. výpočtov s reálnymi číslami apod.

Podrobné sylaby predmetu

(rozčlenenie na jednotlivé body nezodpovedá rozčleneniu na jednotlivé prednášky)

• Základné pojmy teórie: čiastočné a totálne funkcie. Skladanie funkcií. Klony (čiastočných) funkcií. Trojice číslovacích funkcií.
• Operátor primitívnej rekurzie, klon PRec. Konkrétne primitívne rekurzívne funkcie. Operácie, na ktoré je uzavretý. Kódovanie postupností do exponentov. Iné rekurzívne schémy, na ktoré je PRec uzavretý.
• Univerzálne (čiastočné) funkcie. Diagonalizácia. Kódovanie primitívne rekurzívnych funkcií a funkcia pre ne univerzálna. Regulárna minimalizácia. Rekurzívne funkcie. Neohraničená minimalizácia a čiastočne rekurzívne funkcie.
• Primitívne rekurzívne, rekurzívne množiny a predikáty. Rekurzívne spočítateľné množiny a čiastočne rekurzívne predikáty. Uzavretosť tried množín a predikátov na operácie. Ohraničená a neohraničená kvantifikácia. Postova veta.
• Registrové stroje a výpočty na nich. Kódovanie registrových strojov. Univerzálny registrový stroj. Kleeneho veta o normálnej forme. Ekvivalencia vypočítateľnosti a vypočítateľnosti na registrových strojoch.
• Rozšírenie pojmov z číselných množín na jazyky. Výpočty na Turingových strojoch. Churchova téza.
• Indexácia. s-m-n veta. Veta o rekurzii. Charakterizácia rekurzívnych a čiastočne rekurzívnych funkcií pomocou +, ., non-eq, mi. Gamma-kódovanie postupností.
• Problém zastavenia a s ním príbuzné problémy. Redukcie. Nerozhodnuteľné a čiastočne rozhodnuteľné problémy. Riceova a Rice-Shapirova veta.
• Many-to-one redukcia, degrees of unsolvability, kreatívne a prosté množiny. Rekurzívna (ne)oddeliteľnosť. Ohraničenie času výpočtu a počtu registrov stroja.
• Rekurzívne reálne čísla a nerozhodnuteľné problémy v tejto oblasti.
• Aritmetická hierarchia predikátov (Sigma_i, Pi_i). Aritmetická definovateľnosť. Nedefinovateľnosť pravdy. Nerozhodnuteľnosť a neúplnosť aritmetiky. Goedelova veta o neúplnosti.

Ku prednáške je k dispozícii elektronický učebný text

Ivan Korec: Úvod do teórie algoritmov

(Tento elektronický text je prístupný len vrámci FMFI UK - je zakázané prevziať a zverejniť tento text, či už na vlastnej WWW-stránke alebo iným spôsobom, ako aj používať ho na iné účely ako štúdium predmetu Teória vypočítateľnosti na FMFI UK).

Pozor: Budú prednášané (a teda aj skúšané) aj časti, ktoré tento text nepokrýva !!!

Zoznam odporúčanej literatúry

• I. Korec: Úvod do teórie algoritmov, elektronický učebný text.
• A. Maľcev: Algoritmy i rekursivnyje funkcii, Moskva, 1965.
• H. Rogers: Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.
• D. E. Cohen: Computability and Logic, Ellis Horwood, Chichester, 1987.