Course notes in mathematical logic

Computability Theory

Lecture notes for master's students in logic, organized as short courses with explicit prerequisites. They cover classical computability theory and its applications to algorithmic randomness, reverse mathematics and higher computability.

Begin with Models of computation All courses

Courses available: 24
Lessons: 102
Comprehension questions: 384

Turing machine · binary successor

q₀

⊔

start in state q₀ on the first digitinput 11

A Turing machine with two states computing the successor in binary. Each step applies one transition of δ.

Learning tracks

Each track is a main sequence of short courses. Arrows indicate prerequisites within the track; hovering over a course highlights the courses it depends on and those depending on it. Courses in preparation have a dashed border. All courses, including specialized ones, are listed in the catalogue.

From the models of computation to the structure of the Turing degrees: the common basis of the other tracks.

No prerequisites

Models of computation

Turing machines, register machines, partial recursive functions and the λ-calculus, and the equivalence of these models.

13 lessons· 495 min

Countability and diagonalization

Comparison of infinite sets, the Cantor–Bernstein theorem, countable sets, the diagonal argument and the continuum, with their first applications to computation.

6 lessons· 225 min

Foundations

Fundamentals of computability

The enumeration of the partial computable functions, the universal function and the SMN theorem, the halting problem and reductions, c.e. sets, Kleene's fixed point theorem and Rice's theorem.

6 lessons· 235 min

Intermediate

Oracles and Turing degrees

Computation relative to an oracle, Turing reducibility and degrees, the jump, limit computability, the finite extension method, and low and high sets.

6 lessons· 235 min

The arithmetic hierarchy

Classifying sets by the quantifier complexity of their definitions, Post's theorem linking it to the jump, the classification of index sets, arithmetic definability, and codes for sets.

5 lessons· 195 min

Advanced

Post's problem and the priority method

Simple and creative sets, the Friedberg–Muchnik theorem, a low simple set, and the Sacks splitting theorem, by finite injury priority arguments.

4 lessons· 165 min

Π⁰₁ classes

Computable trees, König's lemma, computable members of Π⁰₁ classes, the low, computably dominated and cone avoidance basis theorems, PA degrees, and finitely branching trees.

5 lessons· 200 min

10 specialized courses are not shown in the graphs. Browse them in the catalogue.

Example of a comprehension question

From the lesson The halting problem. The question refers to the following proof.

Suppose that

\emptyset' = \{e : \Phi_e(e)\converge\}

is computable. Let

D

be the algorithm which, on input

x

, decides whether

x \in \emptyset'

, enters an infinite loop if so, and halts with output

0

otherwise; let

d

be an index of

D

.

Then

\Phi_d(x)\converge \iff \Phi_x(x)\diverge

for every

x

, and taking

x = d

yields a contradiction.

Question 1 of 3Select one answer

Where is the hypothesis ” $\emptyset'$ is computable” used?

To make the test " $x \in \emptyset'$ " in $D$ always terminate, so that $D$ halts whenever $\Phi_x(x)\diverge$ .
To show that $D$ has an index.
It is not used.

Question 2 of 3Select one answer

Why is the equivalence $\Phi_d(x)\converge \iff \Phi_x(x)\diverge$ applied with $x = d$ ?

So that the two sides concern the same computation, $\Phi_d(d)$ : the row $d$ disagrees with the diagonal at its own column.
Because $d$ is the least index of $D$ .
Any $x$ would give a contradiction.

Question 3 of 3Select one answer

Which step corresponds to “flipping the diagonal bit” in Cantor’s argument?

$D$ loops on $x$ exactly when $\Phi_x(x)$ halts, and halts exactly when it loops.
Deciding whether $x \in \emptyset'$ .
Choosing an index $d$ for $D$ .

Contributing

The notes are maintained collaboratively. To report an error or propose an improvement, select the relevant passage in a lesson, choose the type of remark, and sign in with ORCID. Remarks are visible to all readers and are reviewed by the maintainers.

Select a passage or a formula in a lesson.
Choose the type of remark: typo, unclear argument, mathematical error, suggestion, or question.
Sign in with ORCID and submit.