Turing's Double Jump & the Long Intervals Problem
After reading this post, in which my mutual @anremithrl discusses a computer science problem with a peer, I was inspired to consider the generalization & its relationship to (non)constructability. I'll be modifying the details of the original problem slightly, to avoid some subtleties which would pop up in the generalization, but hopefully you can see how it's still the same problem.
Consider a computable set X⊆ℕ, so X is implemented by a total computable function sending ℕ→{0,1}. An interval subset of ℕ is any set of the form {k∈ℕ : a≤k≤b}, so basically it's a bunch of consecutive numbers. We're interested in whether X contains intervals of various lengths. For each positive integer n, let f(n)=1 whenever X contains an interval of length n, and otherwise f(n)=0. In the original problem, we had picked a specific set X corresponding to the digits of π, and asked whether or not f is computable. Anremithril proved that f is necessarily computable, using a proof similar to the following.
Theorem: For every computable set X, the corresponding f is computable.
proof: There are two cases. If X contains intervals of arbitrarily long length, then we simply have f(n)=1 for all n. Since f is constant, then obviously f is computable. If this fails, then there must be some maximum size of any interval in X, say N. Then we have f(n)=1 if and only if n≤N, and f(n)=0 otherwise. We easily obtain a computer program which implements f, by just hardcoding N and comparing it to the input. Therefore f is computable.
QED
In the OP, anremithrl points out that this proof is nonconstructive. Formally speaking, this is clear since we have invoked the law of excluded middle at the start. Informally speaking, this is clear because, although we know some algorithm implements f, we don't know which algorithm. Even if we can interrogate X, it's not clear how we could determine what N is, or if it's even finite, and we can't build the program which implements f without that knowledge. If there were a constructive proof, then the proof itself could be converted into a computable function F which takes as input the set X, and produces as output the function f. So, new question: can F be computable? Can there be a constructive proof of this theorem?
After taking interest in the problem, I was able to show that there cannot be any constructive proof. Such F is necessarily uncomputable, and in fact F can solve the halting problem.
Theorem: Let F be a function which takes as input a program implementing a computable set X⊆ℕ, and produces as output a program implementing the function f:ℕ→{0,1} such that f(n)=1 if and only if X contains an interval of size n. Then the halting problem is computable relative to F.
proof: Let M be any Turing machine. Construct a set X⊆ℕ so that n∈X if and only if M has halted after n timesteps. This X is clearly computable, since we can decide whether or not n∈X by just running M for n timesteps and checking if it's halted within that time. More strongly, we can get a computable function G:M↦X which produces this X given M. Now by invoking F, we see that F(G(M))=F(X)=f is a computable function such that f(1)=1 if and only if X contains an interval of size 1. In other words, f(1)=1 if and only if X is nonempty. But X is nonempty if and only if M halts! So F(G(M))(1)=1 if and only if M halts, and since every operation here is computable except possibly F, then the halting problem is computable relative to F.
QED
Okay, so now we know F is uncomputable. My original instinct, at this point, was that F would be equivalent to the halting problem. In other words, that the halting problem then we could perform the function which F is supposed to perform. But is that really true? After investigating it for a while, we were able to get kinda close. It turns out that F is computable provided we have two oracles. This'll be a little more abstract than before, so pardon me for introducing some notation.
Given any set S⊆ℕ, we can imagine a Turing machine which is augmented with an oracle for S. This is like a computer program which has the ability to call some external black-box function, namely S, which tells us which numbers are in the set and which ones aren't. These are called Oracle Turing Machines. Given another set Z, we say Z is "computable relative to S" provided there's an oracle machine which can compute Z when given an oracle to S. We may write Z≼S to denote the relationship. This relation is transitive and reflexive. Since the empty set is already computable then we have ∅≼S for all S, and conversely we have S≼∅ if and only if S is a computable set. In this way, the computable sets are all at the bottom of this ordering, and are understood as being computationally equivalent to ∅.
A common choice of oracle is where S is taken to be the set of (Godel numbers for) computer programs which halt. This can be generalized. Given any set S, consider the set of all OTMs which halt when their oracle is interpreted as being S. This set is denoted S' and is referred to as the Turing jump of S. Notice that we can computably enumerate the set of all OTM programs, since the structure of the program doesn't really change when we change the oracle; only the behavior of the program changes, during runtime. In this way, S' can be understood as being another subset of ℕ.
Lemma: For every set S, we have S≼S' but not vice versa.
proof: The first claim is more trivial. Given any natural number n, we can construct an OTM which uses an oracle for S to check whether n∈S, and then halts if and only if this is true. If we also have an oracle for S', then we can construct that machine and feed it to S' to see if it halts, which effectively decides whether or not n∈S. In this way, S is computable relative to S', so we say S≼S' as claimed.
For the less trivial direction, we basically just use Turing's original proof of the unsolvability of the halting problem, but generalized to the case of OTMs. If we had S' computable relative to S., then there must exist an OTM we'll call H, which takes as input any other OTM, and determines whether or not the input machine halts (all oracles here are just S). Given H, we can construct an OTM whose behavior is as follows: we take as input any OTM, call it M, and provide M as its own input without fully computing it, so we construct a machine which implements M(M). Now we evaluate H(M(M)) to see if evaluating M(M) will halt, and our machine should halt if and only if M(M) does not. Let R denote this machine, then R(R) halts if and only if R(R) does not halt, a contradiction. It follows that S' cannot be computed relative to S.
QED
Given that ∅ is computable, then its Turing jump ∅' can be understood as an oracle to the halting problem. Our second theorem, the first one about F, showed that ∅'≼F because F can be used to solve the halting problem. Our followup question is whether the reverse is true, we want to know if F≼∅' or not. Our partial result, proven below, is that F≼∅'', meaning we can compute F given a double jump.
Theorem: There exists a function F≼∅'' such that, given a computable set X as input, F(X) outputs a computable function f such that f(n)=1 iff X contains an interval of size n.
proof: Let X be any computable set, and let f be the corresponding function as previously, so that f(n)=1 iff X contains an interval of length n. For each natural number n, construct a Turing machine M[n] whose behavior is to perform an unbounded search to see whether or not X contains an interval of length n; so M[n] halts if and only if f(n)=1.
Now construct an oracle machine C using oracle ∅' which performs an unbounded search for some n such that M[n] does not halt; so C halts if and only if there exists an n such that f(n)=0.
Finally we show how to implement F given ∅''. First, given any input set X, construct the corresponding Oracle machine C as above. Now using ∅'' we can determine whether or not C halts. If C does not halt, then f(n)=1 for all n, so F may output a trivial program which just returns 1 for all inputs. If instead C halts, then since ∅'≼∅'', we can just execute C outright to obtain the largest N such that f(n)=1. Once we obtain this N, then we infer f(n)=1 if and only if n≤N, and F may output a computer program which implements f by simply hard-coding N.
QED
This puts a bound on the Turing degree of F, we now know ∅'≼F≼∅''. So F is at least as powerful as the halting problem, and at most as powerful as the second halting problem, but it's not yet clear where exactly F lies between them. After thinking for a few hours more, I figured out the answer! Let's consider the following adjusted problem.
Long intervals problem: Given an arbitrary computable set X, determine whether or not X contains intervals of arbitrarily long lengths.
Theorem: Suppose F takes as input a computable set X, and produces as output a computable f such that f(n)=1 iff X contains an interval of length n. Then the long intervals problem is computable relative to F.
proof: Let X be any computable set. To solve the long intervals problem using F, first evaluate F(X)=f. Since f is computable, we can construct a Turing machine M which performs an unbounded search for a number n such that f(n)=0, and M halts if and only if such n exists. Recall that F can be used to solve the halting problem. Therefore, using F we can determine whether or not M halts. But notice that M halts if and only if X does not contain arbitrarily long intervals! So by using F to construct f, then constructing M, and finally using F to determine if M halts, we can decide whether or not X contains arbitrarily long intervals. It follows that the long intervals problem is computable relative to F.
QED
The long intervals problem is interesting, because it turns out that an oracle to this problem can be used to decide the truth of any Σ_2 sentence in the arithmetical hierarchy (elaboration on what that means below, for the uninitiated).
Theorem: The truth of an arbitrary Σ_2 arithmetical sentence can be decided, given an oracle to the long intervals problem.
proof: Let φ be a sentence which is within Σ_2 of the arithmetical hierarchy. This means φ can be written in the form ∃n∀k ψ(n,k), where the relation ψ is at least computable. To determine whether φ is true, we'll actually consider the negation ¬φ which thus takes the form ∀n∃k¬ψ(n,k). Now, construct a Turing machine M, which can print bits to some output tape, and whose behavior is as follows.
This is computable, since ψ was computable by premise. We also notice that this program prints out an infinite binary string, which works since at every step in the k-loop we are printing "0". This program therefore prints out an infinite and computable binary string, which we may call X, which thus represents a computable set in the natural way. Notice that X contains an interval of length n if and only if there exists some k such that ψ(n,k) is false. Therefore, X contains arbitrarily long intervals if and only if ∀n∃k ¬ψ(n,k). In other words, our formula φ is true if and only if X does not contains arbitrarily long intervals. Therefore, by invoking an oracle to the long intervals problem, we can decide the truth value of φ.
QED
Corollary: Suppose F takes as input a computable set X, and produces as output a computable f such that f(n)=1 iff X contains an interval of length n. Then ∅''≼F.
proof: Recall that F can be used to solve the long intervals problem, and the long intervals problem can be used to construct an oracle which decides the truth of Σ_2 arithmetical sentences, hence F can be used to construct an oracle for Σ_2 truth. It then follows from Post's Theorem that an oracle for Σ_2 truth is equivalent to Turing's double jump ∅''. Therefore ∅'' is computable from F, so that ∅''≼F.
QED
And that's all! We found out that F can be constructed given ∅'', and conversely ∅'' lets us construct such an F, so the two are equivalent in the sense of Turing degrees. In hindsight, I think if my intuition was a little sharper, I could have seen this coming. In the original proof showing that f was computable, allllll the way at the start, we invoked the law of excluded middle on a particular statement: "for all n, X contains an interval of length n", or equivalently "for all n, there exists k, such that k is the beginning of an n-length interval subset of X". If I'd had my thinking cap on earlier, I might have noticed this was plainly Σ_2, and inferred F was likely equivalent to ∅'' right away!
origamiaround
titsay
gummygunk
blakekathryn
janainaart
