The paper in question covers something that I have been meaning to read up for months: the arithmetical hierarchy, which was sadly not covered in the university courses I have attended. If you are into theoretical computer science, you might have come across things like \( \Sigma_2^0 \) or \( \Pi_1^0 \); I have, and while I knew that they had something to do with the arithmetical hierarchy (which I did not know what exactly it was, either), I never got around to read up on what exactly they mean. In particular, this paper examines where sets that make interesting statements about computability theory fit into the arithmetical hierarchy.

From all I can tell, the paper does a very unfortunate mistake when defining the meaning of the two concepts, as it wrongly gives the same definition for both of them. The paper defines a set \( A \) of natural numbers being in both \( \Sigma_n^0 \) and \( \Pi_n^0 \) as \( i \in A \Leftrightarrow \forall k_1 \exists k_2 \ldots R(i, k_1, k_2, \ldots) \), where \( R \) is a computable predicate (otherwise every set would be in \( \Sigma_0^0 \) because every set is representable by a predicate, albeit not by a computable one). Of course, this does not make any sense, and Wikipedia offers a much more believable definition thereof: “Also, a \( \Sigma^0_n \) formula is equivalent to a formula that begins with some existential quantifiers and alternates \( n-1 \) times between series of existential and universal quantifiers; while a \( \Pi^0_n \) formula is equivalent to a formula that begins with some universal quantifiers and alternates similarly.” In this context formula and set is more or less interchangeable, as a formula describes the set of values that satisfy it.

After clearing up this slight confusion, it also becomes possible to understand the rest of the paper. It defines the concept of a \(\Sigma_n^0\)-complete and \(\Pi_n^0\)-complete set as being a set that all sets of the respective class can be reduced to and that is in that class. Let, for example, \(B\) be \(\Sigma_2^0\)-complete, then for every set \( A \in \Sigma_2^0\) there is a computable function \(f\) such that \(i \in A \Leftrightarrow f(i) \in B\).

A few complete sets are given (without proof). I will pick out the example of \( K = \{i: 0^i \in W_i \} \) where \( W_i \) is defined in this paper as the set of words for which the Turing machine of index \( i \) halts. For those unfamiliar with the theory of computation this may be odd, but as every Turing machine can be described by finite string over a finite alphabet, there is a way to enumerate the Turing machines, that is, assign an index to each of them.

It took some time wrapping my head around why this set is \( \Sigma_1^0 \), but essentially it boils down to the fact that it can be expressed by \(i \in K \Leftrightarrow \exists z\; Halts_i(0^i, z) \) where \( z \) expresses (the Gödel number of) a trace of a computation of \( M_i \) and \( Halts_i(j, z) \) is a predicate that is true iff \( z \) is a trace of a halting computation of \( M_i \) on input \( j \); without fancy terms the formula means: an \( i \) is in \( K \) if and only if there exists an execution trace of \( M_i \) that halts on the input \( 0^i \). Well, less fancy terms, I guess.

If you know about computability theory you see I hand-waved a few things. For instance, I just assumed that \( Halts \) is a computable predicate, but it is not hard to imagine that checking whether a trace of a computation on a Turing machine on an input actually is a halting computation is indeed computable (you check whether the last state is a halting state and then check whether all steps of the trace are allowed in the Turing machine). It is also important to note that the restriction to computable predicates is needed for the definition to make any sense, this is because if non-computable predicates are allowed, every set \( A \) would trivially be expressible using zero quantifiers by a predicate \( P(e) \Leftrightarrow e \in A \).

The paper then shows that the set of (indices of) Turing machines that work in time \( n + 1\) relative to the size of their input is \( \Pi_1^0 \)-complete. They first show that the set is in \( \Pi_1^0 \) by showing a formula that represents it. It might be confusing to the reader that their formula is \( \forall n, x, z\; (…) \). At first look one might think “I thought \( \Pi_1^0 \) meant there is one \( \forall \)”. This is a technicality that is not elaborated on in this paper: the universe is assumed to be integers, which are countable. This allows to encode n-tuples as a single integer in various way (e.g. using powers of prime numbers), which are then “decomposed” again by the predicates. The proof that it is complete is done by reducing a set already known to be complete to it (I will omit details to not completely blow the scope of this post).

After this it is also proven that the set of Turing machines that work in polynomial time is \( \Sigma_2^0 \)-complete, the details of which I also refer to the paper. The main idea of the proof is again to prove that it is in \( \Sigma_2^0 \) by showing a formula that expresses it and then reduce an already known to be complete set to it.

There are more proofs about properties of Turing machines and their place in the arithmetic hierarchy which I will not elaborate on in the interest of brevity, if you are interested in this sort of stuff I recommend reading the whole paper. One of them sadly references another paper which is behind a paywall, so it might be hard to really grasp what is going on (one has to trust the statement asserted with a reference to that paper is true).

Anyway, the second section of the paper shows corollaries that can be deduced from the previously proved statements about the arithmetical hierarchy. For example, that there is a Turing machine that works in time \( n + 1 \) but cannot be proved to. This is simply because Turing machines that provably do so can be enumerated by definition – proofs are finite strings over finite alphabets, hence can be enumerated. The set of Turing machines that have the property has previously been proven to be \( \Pi_1^0 \)-complete, which cannot be enumerated. This is, intuitively, because infinitely many elements have to be checked before giving an answer to the \( \forall \).

I will not enumerate the rest of the proofs and corollaries, so take a look at the paper if this incited interest.

Link to the paper: Arithmetical Hierarchy and Complexity of Computation.