Vyčíslitelnost

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

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

s aplikacemi ve formální dokazatelnosti.

Požadavky:

Elementární aritmetika, 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:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-VYC/

Další informace:

https://courses.fit.cvut.cz/NI-VYC/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. obor Znalostní inženýrství, 2016-2017 (volitelný předmět)
• Mgr. obor Počítačová bezpečnost, 2016-2019 (volitelný předmět)
• Mgr. obor Počítačové systémy a sítě, 2016-2019 (volitelný předmět)
• Mgr. obor Návrh a programování vestavných systémů, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Informační systémy a management, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. program Informatika, pro fázi studia bez oboru, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Systémové programování, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Teoretická informatika, 2016-2017 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2018-2019 (volitelný předmět)
• Mgr. obor Znalostní inženýrství, 2018-2019 (volitelný předmět)