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

Computability

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

Classical theory of recursive functions and effective computability.

Požadavky:

Basic course in logic.

Osnova přednášek:

1. Introduction. Elementary recursive functions.

2. Primitive recursive functions. Ackermann function.

3. General recursive functions. Universal functions.

4. Partial recursive functions.

5. Turing machines.

6. The power of Turing machines.

7. Universal machine. Halting Problem.

8. The equivalence of Turing machines and recursive functions.

9. Arithmetics: coding the language.

10. Recursive axiomatization.

11. (In)completeness and (un)decidability.

12. Diagonal lemma, Gödel's theorem.

Osnova cvičení:

1. Elementary recursive functions.

2. Primitive recursive functions

3. General recursive functions.

4. Partial recursive functions.

5. Turing machines.

6. Programming Turing machines.

7. Programming Turing machines.

8. Programming Turing machines.

9. Gödel coding and decoding.

10. Decidability: examples.

11. Undecidability: examples.

12. Diagonalization.

Cíle studia:

The basic formalizations of an „algorithm“ and elementary questions of computability.

Studijní materiály:

1. Church: An unsolvable problem of elementary number theory

2. Church: A note on the Entscheidungsproblem

3. Davis: Computability and unsolvability

4. Enderton: Elements of Recursion Theory

5. Kleene: Introduction to Metamathematics

6. Rogers: Theory of Recursive Functions and Effective Computability

7. Shoenfield: Mathematical Logic

8. Turing: On computable numbers

9. Č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:
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 30. 8. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6699806.html