Computability (2024)
(Jan Starý, jan.stary@fit.cvut.cz)
The goal of the lecture is to master the two classical formalizations of computability, namely recursive functions and Turing machines, and possibly others (register machines, Markov algorhitms). The rest of the semester is devoted to applications, mostly connected to computer science and mathematical logic (arithmetical coding, undecidability, Gödel theorems).
literature
The topic originated in the 1920s, so there is a load of classical literature by now.
For computability and recursion:
- Enderton: Elements of Recursion Theory (Part C.1 of J. Barwise: Handbook of Mathematical Logic)
- Enderton: Computability Theory
- Kleene: Introduction to Metamathematics (Part III: Recursive Functions)
- Kleene: Origins of Recursive Function Theory
- Mendelson: Introduction to Mathematical Logic (Chapter 5, Effective Computability)
- Monk: Mathematical Logic (Part I: Recursive Function Theory)
- Rogers: Theory of Recursive Functions and Effective Computability
For connections to arithmetic and logic:
- Church: A note on the Entscheidungsproblem
- Church: An Unsolvable Problem of Elementary Number Theory
- Kleene: Mathematical Logic (Chapter V: Computability and Decidability)
past
- 20.02. Turing machines.
- 27.02. elementary recursive functions and relations.
- 05.03. prime coding; primitive recursion, iterated powers.
- 12.03. general recursive functions; a universal coding function.
- 19.03. partial recursive functions
- 26.03. encoding machines with recursive functions and vice versa.
- 02.04. universal function; recursive enumerability;
- 09.04. computing codes: parameter theorem, Rice theorem. Markov rewriting.
- 16.04. aritmetization of syntax, Gödel incompleteness
plan
- 23.04. representability
- 30.04. Löb conditions, improvability of consistence.
- 07.05.
- 14.05. (Dean’s Day)
seminar
Here I will list the homework assignments supposed to be presented in the seminar (counting towards seminar credit).
- Implement the Turing machine for the successor, addition, maximum.
- Implement the Turing machine which encodes words of {a,b,c} in binary.
- Find the rank of the factorial, polynomials, and other everyday functions with respect to the tower function.
- Show how the rank grows for the sum and the product.
The following emulators might be helpfull when implementing various machines:
grades
To pass NIE-VYC means to get seminar credit and to pass an exam.
In the lectures and seminars, I will assign small tasks, give examples without proof, skip easy parts of proofs etc, to be presented on the seminar. The aim is for the seminar to be mostly done by students.
The exam consists of two "computational" tasks (typicaly: construct a given machine, show that a function is recursive) finalizing the seminar credit, and two "theoretical" questions (typically: definition, theorem, proof). In the theoretical questions, the aim is to present an understanding of fundamental notions and theorems and the main ideas of proofs - as opposed to technicalities or long laborious inductions.
In case someone takes a particular interest in a topic, they can suggest one of these two theoretical questions, modulo my agreement.
exam terms
An exam term is any day that works for you and me, given that I know about it a day or two before.