Computability

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Applied Mathematics

Synopsis:

Classical theory of recursive functions and effective computability,

with applications in provability theory.

Requirements:

Elementary arithmetics, a 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:

Church: An unsolvable problem of elementary number theory

Church: A note on the Entscheidungsproblem

Davis: Computability and unsolvability

Enderton: Elements of Recursion Theory

Kleene: Introduction to Metamathematics

Rogers: Theory of Recursive Functions and Effective Computability

Shoenfield: Mathematical Logic

Turing: On computable numbers

Černý: Výpočty I

Note:

Further information:

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

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master branch Knowledge Engineering, in Czech, 2016-2017 (elective course)
• Master branch Computer Security, in Czech, 2016-2019 (elective course)
• Master branch Computer Systems and Networks, in Czech, 2016-2019 (elective course)
• Master branch Design and Programming of Embedded Systems, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Info. Systems and Management, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Software Engineering, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Web Engineering, in Czech, 2016-2019 (elective course)
• Master program Informatics, unspecified branch, in Czech, version 2016-2019 (elective course)
• Master branch System Programming, spec. System Programming, in Czech, 2016-2019 (elective course)
• Master branch System Programming, spec. Computer Science, in Czech, 2016-2017 (elective course)
• Master specialization Computer Science, in Czech, 2018-2019 (elective course)
• Master branch Knowledge Engineering, in Czech, 2018-2019 (elective course)