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

Vyčíslitelnost

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

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

Požadavky:

Základní kurs logiky.

Osnova přednášek:

1. Úvod a motivace. Elementárně rekursivní funkce.

2. Primitivně rekursivní funkce. Ackermannova funkce.

3. Obecně rekurzivní funkce. Universální funkce.

4. Částečně rekurzivní funkce.

5. Turingovy stroje.

6. Výpočetní síla Turingových strojů.

7. Universální stroj. Halting problem.

8. Ekvivalence Turingových strojů a rekursivních funkcí.

9. Aritmetika: kódování jazyka.

10. Rekursivní axiomatisovatelnost.

11. (Ne)úplnost a (ne)rozhodnutelnost.

12. Diagonální lemma, Gödelovy věty.

Osnova cvičení:

1. Elementárně rekursivní funkce.

2. Primitivně rekursivní funkce

3. Obecně rekurzivní funkce

4. Částečně rekurzivní funkce.

5. Turingovy stroje.

6. Programování Turingových strojů.

7. Programování Turingových strojů.

8. Programování Turingových strojů.

9. Gödelovo kódování a dekódování.

10. Rezhodnutelnost: příklady.

11. Nerozhodnutelnost: příklady.

12. Diagonalizace.

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:
https://courses.fit.cvut.cz/MI-VYC/
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 14. 10. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3315506.html