Computability Theory

Computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. A central question of computer science is to address the limits of computing devices by understanding the problems we can use computers to solve. One of the triumphs of 20th century mathematics is that it is possible to show clear limits to the ability of computers, even given arbitrarily vast computational resources, to solve even seemingly simple problems.

While most of the fundamental research problems have been dealt with, computability theory remains an active field of research and is commonly used to discover the computational expressiveness of new ideas in computer science, mathematics and physics.

The aim of this project is to acquaint the student with the fundamentals of computability theory and treat at least one subject of intermediate difficulty. This knowledge will come in handy at the graduate level as questions concerning computability, The Halting Problem, Turing machines, etc., permeate all branches advanced computer science. In addition, the student will be able to distinguish between what can, and what cannot be done with computers, whether they be desktop machines, Turing machines, humans, DNA computers, collections of membranes, or unspeakable alien devices from beyond the pale.

The project is of a purely theoretical nature, and some mathematical maturity is required. Matematisk bifag is an advantage, but not a prerequisite.

The project report should:

• Give a basic account of Turing Machines and Recursive Function Theory (aka. Recursion Theory), and prove the expressiveness of two equivalent (part of the Church-Turing thesis).

• Within Recursion Theory, treat the following classical results: (Unsolvability of) the Halting Problem, the smn-Theorem, the Recursion (or fixpoint) Theorem, Rice's Theorem and the Kreisel-Lacombe-Shoenfield Theorem.

Literature for the above will be excerpts from classical textbooks in the area, e.g. [2,7,6,5]

In addition, the report should treat exactly one of the following - wonderful - extra subjects:

• Independence results for formal theories on the basis of computability theory, e.g.: Find a context-free grammar G such that the question of whether G generates all strings over its alphabet is independent of ZFC (easier than it sounds [4]).

• Real analysis using computability theory, e.g. computable real numbers, basic undecidability results for them, general computable metric spaces, and possibly the Tseitin-Moschovakis Theorem [8].

• The Arithmetical Hierarchy, the standard generalization of computability theory using oracles (this will also require giving a basic account of first-order logic) [7,6].

• Equivalence of the expressibility of Turing machines/Recursive Function Theory with other models of computation, e.g. counter machines or lambda calculus. Students with a knack for adventure might tackle more exotic computational paradigms, e.g. Conway's language FRACTRAN [1], or the programming language BRAINFUCK [3].