Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Vyčíslitelnost

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-VYC Z,ZK 4 2+2 česky
Přednášející:
Jan Starý (gar.)
Cvičící:
Jan Starý (gar.)
Předmět zajišťuje:
katedra aplikované matematiky
Anotace:

Klasická teorie rekursivních funkcí a efektivní vyčíslitelnosti.

Rekursivní funkce, Turingovy stroje, vztah mezi nimi. Churchova teze.

Universální stroj, normální forma. Halting Problem a pevné body.

Vztahy s logikou a aritmetikou: (ne)úplnost a (ne)rozhodnutelnost.

Požadavky:

Základní povědomí o množinových pojmech a operacích

(relace, zobrazení, uspořádání, ...) a vlastnostech přirozených čísel, zkušenost s programováním.

Výhodou je absolvování základního kurzu logiky.

Osnova přednášek:
Osnova cvičení:
Cíle studia:

Získat přehled o základních formalizacích pojmu „algoritmu“ a elementárních otázkách vyčíslitelnosti.

Studijní materiály:

Church: An unsolvable problem of elementary number theory

Church: A note on the Entscheidungsproblem

Davis: Computability and unsolvability

Enderton: Elements of Recursion Theory

Kleene: Introduction to Metamathematics

Rogers: Theory of Recursive Functions and Effective Computability

Shoenfield: Mathematical Logic

Turing: On computable numbers

Černý: Výpočty I

Poznámka:
Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 20. 4. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3315506.html