Prerekvizity
Od ľudí, ktorí si tento predmet zapíšu, sa očakávajú približne nasledovné znalosti:
- Vie zostrojiť konečný automat aj Turingov stroj a dokázať o nich, že robia to čo chce.
- Videl už aspoň jeden nerozhodnuteľný a aspoň jeden čiastočne rozhodnuteľný problém.
- Pozná rozdiel medzi spočítateľne a nespočítateľne nekonečnými množinami.
Ciele
Absolvent predmetu by mal rozumieť nasledujúcim výsledkom:
- Churchova-Turingova téza. Ukazuje sa, že väčšina rôznych spôsobov definovania algoritmickej vypočítateľnosti vedie k rovnako silným výpočtovým modelom. Napriek tomu je dobré poznať viacero modelov, lebo nám umožňujú rôzne uhly pohľadu -- a to, na čo sa chceme pozerať, je otázka, čo vlastne vieme a nevieme robiť na bežných počítačoch v bežných programovacích jazykoch.
- Primitívna rekurzia. Keď zakážeme niektoré konštrukcie programovacieho jazyka, ako napr. rekurziu a while-cykly, obmedzíme sa tým -- ale ešte stále skoro všetko budeme vedieť robiť. Ľubovoľný algoritmus sa dá prepísať na ekvivalentný s najviac 1 while-cyklom.
- Veta o rekurzii. V ľubovoľnom klasickom programovacom jazyku sa dá ľubovoľný program upraviť tak, aby si v nejakej premennej zostrojil zdrojový kód seba samého. Medzi aplikácie patria finty robené niektorými počítačovými vírusmi.
- Nemožnosť "mechanizácie" matematiky. Pri skoro žiadnej rozumnej teórii si nemôžeme byť istí jej bezospornosťou, presnejšie ju nevieme dokázať v rámci tej teórie. Neexistuje algoritmus, ktorý by nám o ľubovoľnom tvrdení vedel povedať, či je pravdivé. A takisto neexistuje algoritmus, ktorý by nám o ľubovoľnom tvrdení vedel povedať, či je dokázateľné.
- Hranica vypočítateľnosti. Existujú "najťažšie" algoritmicky riešiteľné problémy. Zložitosť problémov vieme porovnávať pomocou rôznych redukcii. Aj za hranicou vypočítateľnosti existuje hierarchia rôzne ťažkých problémov.
Syllabus
(Témy označené *** sa zatiaľ neprednášali, ale v prípade záujmu a dostatku času vedia byť zaradené.)
- História vypočítateľnosti a súvisiacich otázok. Nádeje (Leibniz, Frege, Hilbert) a ich dokonalé rozbitie (Russell, Gödel, Turing, Church, Tarski).
- Prehľad základných automatových modelov algoritmickej vypočítateľnosti: Turingove stroje, Minského registrové stroje, Single instruction computer, modifikovaný Pascal.
- Prehľad základných gramatikových modelov algoritmickej vypočítateľnosti: Frázové (type-0) gramatiky, Markovove algoritmy, Postove tag systémy. Celulárne automaty, game of life, Wangove dlaždice.
- Funkcionálne modely vypočítateľnosti: Čiastočne rekurzívne funkcie, *** Lambda kalkulus, *** Kombinátorová logika.
- *** Lambda kalkulus detailnejšie: notácia, univerzálnosť, beta redukcia, fixpointy a rekurzia. Aplikácie v moderných programovacích jazykoch.
- Rekurzívne a čiastočne rekurzívne funkcie. Primitívna rekurzia ako obmedzenejší model vypočítateľnosti a jej súvis s programmi bez while-cyklov. Rekurzívne množiny a predikáty.
- Kódovanie konečných postupností celých čísel. Aritmetizácia syntaxe.
- Za hranicou: Ackermann, Busy Beaver, univerzálne funkcie.
- *** Veta o rekurzii. Quines (programy, ktoré vedia vypísať samé seba).
- Redukovateľnosť (one to one, many to one, Turingovská).
- Gödelova veta o neúplnosti a Tarského veta o nedefinovateľnosti pravdy.
- *** Aritmetická hierarchia.