Computability
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
NIE-VYC | Z,ZK | 4 | 2P+2C | anglicky |
- Garant předmětu:
- Jan Starý
- Přednášející:
- Jan Starý
- Cvičící:
- Jan Starý
- 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/
- Rozvrh na zimní semestr 2022/2023:
- Rozvrh není připraven
- Rozvrh na letní semestr 2022/2023:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Předmět je součástí následujících studijních plánů:
-
- Master specialization Software Engineering, in English, 2021 (volitelný předmět)
- Master specialization Computer Security, in English, 2021 (volitelný předmět)
- Master specialization Computer Systems and Networks, in English, 2021 (volitelný předmět)
- Master specialization Design and Programming of Embedded Systems, in English, 2021 (volitelný předmět)
- Master specialization Computer Science, in English, 2021 (volitelný předmět)
- Study plan for Ukrainian refugees (volitelný předmět)