Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2022/2023
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Computability

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
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
místnost TH:A-s135
Starý J.
11:00–12:30
(přednášková par. 1)
Thákurova 7 (FSv-budova A)
As135
místnost TH:A-942
Starý J.
12:45–14:15
(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
St
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 5. 6. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6699806.html