The Problem of Intermediate Recursively Enumerable Turing Degrees

The Turing degree of a set of natural numbers is a concept from computer science and mathematical logic that is a measure of the level of algorithmic unsolvability of the set. This post written by our friends from the ‘Mind vs Trash’ VK-community carries you deeper to the problem of the undecidable languages and the halting problem.

In computability theory, it is common to introduce the class of decidable languages first, and after that, prove that there are undecidable languages as well. There are two common ways to show it: a non-constructive proof (there is an uncountable number of subsets of ΣΣ* and there is a countable number of decidable subsets) and a constructive proof (one or another way of defining the halting problem). After that, it is common to prove that a lot of more ‘natural’ problems are undecidable, but all of them are basically reduced to the halting problem. It can be shown that the set of undecidable languages built this way is countable as well. Here a natural question appears: what about all other undecidable languages since there are so many of them?

The illustration of the Halting problem.

For languages AA and BB, AA is Turing reducible to BB (ABA ≤ B) if AA is decidable with an oracle for BB. Languages are Turing equivalent (ABA ≡ B) if ABA ≤ B and BAB ≤ A. The ≡ relation determines equivalence classes, or Turing degrees. The set of all decidable languages is one equivalence class, while the set of all undecidable languages which are Turing equivalent to the halting problem, is another. Let us try to find more classes.

Let us assume there is an oracle OO for the halting problem. For a program and an input, we can determine in constant time, whether the program will halt on the input. Note, that OO takes as input a program without an oracle, but a program that uses OO (in a meaningful way) cannot be rewritten without OO (it is not a real program as its oracle contains something non-computable), thus, such a program cannot be given as input to an oracle for determining, whether it will halt. Can it be determined, whether an arbitrary ‘program’ with such an oracle will halt (OO can be used for the solution as well)? The answer is: of course not. The proof is analogous to the proof of the halting problem undecidability (the proof is relativising, i.e., adding an oracle will not change it). It means, such a ‘super-halting’ problem is not Turing reducible to ‘normal’ undecidable languages, and it determines the third equivalence class.

Using an oracle for this new problem, we can build the fourth equivalence class, then the fifth, and so on. For an arbitrary Turing degree, its ‘+1’ can be defined as the Turing equivalence class of the halting problem relativised for the given Turing degree. Such an operation is called the Turing jump. It is usually denoted by a prime symbol. If the Turing degree containing decidable languages is 0, then we have the following simple case:

  • Turing degree 0 (decidable languages),
  • 1 = 0’ (reducible to the halting problem),
  • 2 = 1’ = 0’’ (reducible to the super-halting problem),
  • etc.

Is there anything in between?

Friedberg and Muchnik (1956) independently proved that there exists a pair of languages AA and BB, such that both are decidable with an oracle for the halting problem, but AA is undecidable with an oracle for BB, as well as BB is undecidable with an oracle for AA. This result instantly complicates the structure of languages: we see that Turing degrees do not have a total order, and there are also intermediate degrees.

Today it is known that Turing degrees form a lower semilattice with a lot of interesting properties, such as:

  • The cardinality of every Turing degree is countable.
  • There is an uncountable number of different Turing degrees.
  • For any degree aa there is no more than a countable number of degrees bab ≤ a and uncountable number of degrees cac ≥ a.
  • There are nonzero degrees without intermediate degrees between them and zero, i.e., the lattice is not dense ordered.
  • For any degree aa there is a degree bb such that a<ba < b and a=ba′ = b′, i.e., the Turing jump is not similar to the normal ‘+1’ operation!).
  • There is an infinite sequence aia_i of degrees such that aiai+1a_i ≥ a_{i+1}'.
  • For every degree aa there is a degree strictly between aa and aa' (in fact, there is a countable sequence of pairwise incomparable degrees between aa and aa').
References:
  1. Scott Aaronson, Quantum Computing Since Democritus, Lecture 4
  2. S. Barry Cooper, Computability Theory, pp. 219-246
  3. https://en.wikipedia.org/wiki/Turing_degree
  4. https://en.wikipedia.org/wiki/Turing_jump
The Problem of Intermediate Recursively Enumerable Turing Degrees
Banner that links to Serokell Shop. You can buy cool FP T-shirts there!
More from Serokell
quantum computing capabilitiesquantum computing capabilities
Rapid introduction to modal logic, part 2Rapid introduction to modal logic, part 2
Insane Properties of the Closed Long Ray and the Long LineInsane Properties of the Closed Long Ray and the Long Line