Computability

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:

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

Poznámka:

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

Další informace:

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

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

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)
• Master Specialization Digital Business Engineering, 2023 (volitelný předmět)
• Master Programme Informatics, unspecified Specialization, in English, 2021 (volitelný předmět)
• Master specialization Computer Science, in English, 2024 (volitelný předmět)