Description:

Classical theory of recursive functions and effective computability.

Contents:

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.

Seminar contents:

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.

Recommended literature:

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

Keywords:

computability Church's Thesis recursive function Turing machine Halting Problem decidability incompleteness

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar