Computability

Course guarantor:

Jan Starý

Lecturer:

Jan Starý

Tutor:

Jan Starý

Supervisor:

Department of Applied Mathematics

Synopsis:

Classical theory of recursive functions and effective computability.

Requirements:

Basic course in logic.

Syllabus of lectures:

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.

Syllabus of tutorials:

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.

Study Objective:

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

Study materials:

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

Note:

Further information:

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

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Master specialization Software Engineering, in English, 2021 (elective course)
• Master specialization Computer Security, in English, 2021 (elective course)
• Master specialization Computer Systems and Networks, in English, 2021 (elective course)
• Master specialization Design and Programming of Embedded Systems, in English, 2021 (elective course)
• Master specialization Computer Science, in English, 2021 (elective course)
• Study plan for Ukrainian refugees (elective course)
• Master Specialization Digital Business Engineering, 2023 (elective course)
• Master Programme Informatics, unspecified Specialization, in English, 2021 (elective course)
• Master specialization Computer Science, in English, 2024 (elective course)