Quick recap: previously, we defined recursive enumerable (r.e.) sets, which are sets that are generated by a computable function. These sets encode a degree of complexity within them. Specifically, the membership \(x \in A \) is a semi-recursive relation, which means if indeed, \(x\) is in \(A\), then we will know eventually, but if \(x \not\in A\), we may have to wait forever to figure that out. An example is the set \(K = \{e \mid \phi_e(e)\downarrow\}\) , where \(e \in K \iff\) the \(e\)-th program, run on the input \(e\), will halt. If the program halts, then we can confidently say that \(e \in K\), but otherwise we would need to wait forever. In automata theory, this is equivalent to saying that this set is Turing-recognizable.
The process of reduction is common in complexity theory and computability theory, as well as many other theoretical applications. Here, we say that \(A \leq_T B\) if we can figure out membership of \(A\) by a recursive program containing calls to membership of \(B\) as an oracle. Along with Turing reducibility, there is also $m$-reducibility, $1$-reducibility, etc. Turing reducibility, however, to us theoretical computer scientists, make the most sense. This idea allows us to bridge relationships between sets using a computer program, say, written in C, and indeed, Turing reducibility is one of the hotter topics in modern computability due to its interesting structure.
This time, we will give an ambitious attempt to prove the famous Post’s Problem, which asks if there are two r.e. sets that are not Turing reducible to each other. We will prove a weaker variant here that does not require these sets to be r.e., and then introduce the concept of finite injury priority argument to solve it under computable conditions.
#Some Setup
Since Turing reducibility allows us to ask arbitrary number of questions about \(x \in B\). What sets are computable, now that we have this oracle? If \(B\) is something boring like \(\mathbb{N}\) or \(\emptyset\), in which case it would output true or false always, then we intuitively would not add any complexity to recursive programs. However, if \(B\) tells us whether \(\phi_e(x)\downarrow\), for any \(e, x\), then it gets a little more interesting.
Recall that our previous theorem from Kleene (here) that states the following:
We can extend this to our new oracle machines, which use not only \(S, Pd\) in its function calls, but also some \(g : \mathbb{N} \to \{0,1\}\), where \(g(x) = 1\) if \(x \in B\), and \(0\) otherwise(this is also called the characteristic function of the relation). Recall from the definition of \(g\) that it is total and its image is the set \(\{0,1\}\). Once again, since we didn’t even specify the coding details for Kleene’s original theorem, I will only provide the intuition:
We originally mapped the description of the computable functions to the natural numbers. A description of the functions is essentially like ASCII for python code for example, and what we can do is simply add a new ASCII representation of \(g\). Intuitively, before our python interpreter sees the following code:
def do_something():
return S(S(S(Pd(2)))) # Should return 4
def do_something_else():
return g(S(S(0))) # Uh oh! Our interpreter doesn't know what g is
And it fails because of NameError: name 'g' is not defined. However, assume now that the python standard library has the definition for g as an oracle, and we can simply call it.
Now you may ask, “Ray, what does this have anything to do with trying to solve Post’s problem?”. I know, it seems a little off-topic that I would bring programming into this abstract concept. The point I’m trying to make is that upon having access to \(g\), our programs don’t look much different. They can still be represented by finite length strings. This means that the list of programs that can be created using our new functions is still countable. Recall how we used countability to reach a contradiction for the halting problem? We constructed a function, so it must’ve been some \(n\)-th function in the countable enumeration. But the definition of the function makes it different from every other function, so it can’t be the \(n\)-th function. Our construction of two sets that are not Turing-reducible to each other is similar, and the below is a quick tl;dr intuition:
We will construct two sets \(A,B\) incrementally. Let their characteristic functions \(g_A, g_B\) denote whether \(x \in A\), \(x \in B\) respectively. We know that programs using the characteristic functions \(g_A, g_B\) can be enumerated, so we enumerate the functions \(\phi^A_1,\phi^A_2,...\) and \(\phi^B_1, \phi^B_2,...\). We want to construct \(g_A\) and \(g_B\) such that at every input \(e \in \mathbb{N}\), either \(\phi^A_e(x) \uparrow \forall x \in \mathbb{N}\), or \(\exists x, \phi_e^A(x) \downarrow \neq g_B(x)\) and similarly, \(\phi_e^B(x) \downarrow \neq g_A(x)\). This construction guarantees that the characteristic functions of both sets are not computable using the other’s characteristic function. Recall what Turing reducibility means, then this implies \(A \not\leq_T B \& B \not\leq_T A\). So let’s construct the functions \(g_A\) and \(g_B\)!
“You will not find a single \(\mu\) operator or \(T\) predicate in modern computability research” - Kirill Gura (114C TA)
The way we construct \(g_A\) and \(g_B\) will be explained rigorously but in english and programming terms. We define \(g_A\) and \(g_B\) in stages:
At stage 0 (Base):
Case 1: \(\phi_0^A(x) \uparrow \forall x\), define \(g_B(0) = 0\). Obviously, \(g_B \neq \phi_0^A\), since \(g_B(0) \downarrow \& \phi_0^A(0) \uparrow\). We define \(x_0 = 0\).
Case 2: \(\exists x_0, \phi_0^A(x_0) \downarrow\), then if \(\phi_0^A(x_0) = 0 \implies g_B(x_0) = 1\), and \(\phi_0^A(x_0) \neq 0 \implies g_B(x_0) = 0\). Then similarly, \(g_B \neq \phi_0^A\), since \(g_B(x_0) \neq \phi_0^A(x_0)\). Since we defined \(g_B(x_0)\), we can also arbitrarily set \(g_B(y) = 0 \forall y < x_0\).
We perform the same procedure for \(g_A\) and \(\phi_0^B\), and if case 2 occurs for \(g_A\), we obtain a \(y_0\) similar to the \(x_0\) above. We now have an initial segment of \(g_A\) up to \(y_0\) and \(g_B\) up to \(x_0\) in the first step.
At stage \(e+1\) (Inductive):
Case 1: \(\phi_{e+1}^A(x) \uparrow \forall x > x_e\), then we simply define \(g_B(x_e + 1) = 0\), similar to the base case. \(g_B \neq \phi_{e+1}^A\), since \(g_B(x_e + 1) \downarrow \& \phi_{e+1}^A(x_e + 1) \uparrow\). Define \(x_{e+1} = x_e + 1\).
Case 2: \(\exists x_{e+1} > x_e, \phi_{e+1}^A(x_{e+1}) \downarrow\). Then similarly, \(\phi_{e+1}^A(x_{e+1}) = 0 \implies g_B(x_{e+1}) = 1\), and \(\phi_{e+1}^A(x_{e+1}) \neq 0 \implies g_B(x_{e+1}) = 0\), and so they must not be the same. We then set \(g_B(y) = 0 \forall x_e < y < x_{e+1}\).
We do the same procedure for \(g_A\) and \(\phi_{e+1}^B\). Now that we have defined the procedure above inductively, let us now prove by diagonalization that these two sets \(A,B\) are not Turing reducible to each other.
Let us suppose for a moment that \(A \leq_T B\), that is, the membership function of \(A\) can be defined as a recursive program containing calls to membership of \(B\). Then, formally, \(g_A \in \textbf{R}(\mathbb{N}, 0, 1, S, Pd, g_B)\). By Kleene’s theorem which states that we can enumerate the countably many computable functions in the oracle machine, we know that \(g_A\), then must be \(\phi_e^B(x)\), for some \(e \in \mathbb{N}\). However, let’s look at the \(e\)-th step of our inductive construction - we explicitly stated that \(g_A \neq \phi_e^B\)! Then this must be a contradiction, and we can apply the same contradiction with \(g_B\) and \(\phi_e^A\). Thus our constructed sets \(A, B\) are not Turing reducible to each other, so we’re done.
The astute reader, at this point, would be frustrated - “I see you’ve constructed these two sets, but how can you say that they are r.e.?” Actually they’re not. The predicate \(\phi_e^A(x) \uparrow \forall x\) and its variants used during the inductive and base steps are not computable. This is literally asking “will all inputs to \(\phi_e^A\) never halt?”, to which we can’t answer in finite time.
So why did I do all this? Because although our construction was not of r.e. sets, we showed that \(\leq_T\) is not a total order defined on all subsets of natural numbers. In addition, the proof we will introduce next time is an incremental improvement on the intuitions introduced this time. So stay tuned for the r.e. version!