Friedberg–Muchnik theorem

We write A_n \uparrow A to denote that A_0 \subset A_1 \subset \cdots, and A = \lim_n A_n. We will always assume by default that A_0, A_1, \dots are finite. An oracle is a subset A \subset \N. To make an inquiry to an oracle is to ask whether j \in A. The response is "j \in A" xor "j \not\in A". H is the halting oracle. \leq_T is Turing reducibility. TM_i is the i-th Turing machine. TM_i^A is the i-th Turing machine equipped with an oracle for set A. TM_i^A(j) is the output of TM_i^A upon input j. If the machine does not halt, then define TM_i^A(j) = \bot. TM_i^A(j)[k] is the output of TM_i^A upon input j, if the machine halts within k steps. If it has not yet halted, then define TM_i^A(j)[k] = \bot. This definition ensures TM_i^A(j) = \lim_k TM_i^A(j)[k]. \phi_i^A(j) is the largest number that would ever be inquired by TM_i^A while it is computing TM_i^A(j). If TM_i^A(j) = \bot, then define \phi_i^A(j) = \bot. == Kleene–Post theorem ==

The theorem is proven by constructing a Turing machine equipped with H as its oracle, such that: • It streams out a sequence of binary strings \alpha_0, \beta_0, \alpha_1, \beta_1, \dots. • Each \alpha_{n+1} extends \alpha_{n}. • The characteristic function of A is \chi_A := \lim_n \alpha_n. • Similarly for B. • All requirements R_{0,A}, R_{0,B}, R_{1,A}, R_{1,A}, \dots are satisfied. • R_{i,A} states that "The i-th Turing machine, equipped with B as oracle, fails to decide A". • Similarly for B. Each R_{i,A} can be satisfied in two ways: • Negatively, if TM_i^B (the i-th Turing machine, equipped with B as oracle) fails to halt on some input. • Positively, if TM_i^B halts on some input j and outputs a value different from \chi_A(j). Such j is called a witness to R_{i,A}. The construction uses the priority method: The machine streams out \alpha_0, \beta_0, \alpha_1, \beta_1, \dots one by one, such that the requirements R_{0,A}, R_{0,B}, R_{1,A}, R_{1,A}, \dots are satisfied one by one in stages. At stage 2n: • \alpha_0, \beta_0, \dots, \alpha_{2n-1}, \beta_{2n-1} have already been constructed so far, and we seek to construct \alpha_{2n}, \beta_{2n}. • Construct a Turing machine as follows: • For each possible binary string \beta' that extends \beta_{2n-1}, it tests whether the n-th Turing machine would halt on input n given \beta' as its oracle, without attempting to read any bit outside of \beta'. • As soon as such a machine is found, it outputs \beta' and halts. • Then the halting oracle is consulted to see if the previously constructed Turing machine halts. • If it halts, then run it, and assign \beta_{2n} to its output \beta'. After that, compute TM_n^{\beta_{2n}}(n), and assign \alpha_{2n} = \alpha_{2n-1} \oplus b, where b \in \{0, 1\} is chosen to be different from TM_n^{\beta_{2n}}(n). This satisfies R_{n,A} positively. • Otherwise, it does not halt, indicating that all possible \chi_B that extends the current \beta_{2n-1} will necessarily cause TM_n^B(n) to hang forever, thus meaning that R_{n,A} will be satisfied negatively no matter which \chi_B we end up with. In that case, just define \alpha_{2n} := \alpha_{2n-1} \oplus 0,\; \beta_{2n} := \beta_{2n-1} \oplus 0, or whatever. Stage 2n+1 is done similarly to satisfy R_{n,B}. == Friedberg–Muchnik theorem ==

The above construction uses the halting oracle, so the two sets A, B might not be enumerable. It can be strengthened: The theorem can be proved by constructing a Turing machine without oracle such that: • It streams out a sequence of finite sets A_0, B_0, A_1, B_1, \dots such that A_n \uparrow A, B_n \uparrow B, and similarly for B. • All requirements R_{0,A}, R_{0,B}, R_{1,A}, R_{1,A}, \dots are satisfied. • R_{i,A} states that "The i-th Turing machine, equipped with B as oracle, fails to decide A". Similarly for B. Each R_{i,A} can be satisfied in two ways as before. Negatively without a witness, or positively with a witness. Finite injury method The idea of the finite injury method is that we will optimistically hope that the sets we have constructed so far are good enough, and will procrastinate on change for as long as possible, until a requirement gets "injured" (as they must eventually). The injury is positive evidence that our optimism has failed. So we reluctantly update the sets, healing the requirement, update some witnesses, then optimisitically hope all over again. Because there are infinitely many requirements, healing a requirement might clobber other requirements. Specifically, if we ever change our mind about what should go into A, then that would change the behavior of TM_i^A for some i, which might then injure some previously satisfied requirements. To bypass this difficulty, the finite injury method ensures: • Every requirement can be healed infinitely often, because it has an infinite pool of witnesses to choose from. • Every requirement can be injured only finitely often, because we arrange the requirements in a well-ordered set of priorities R_{0, A} \prec R_{0, B} \prec \cdots, and ensure that every requirement can only be clobbered by requirements prior to it. Thus, all requirements will be satisfied in the end. Proof We computably partition \N into infinitely many infinite sets. For example, we can define them by repeated bisection:\{0, 2, 4, 6, \dots\} \cup \{1, 5, 9, 13, \dots\} \cup \{3, 11, 19, 27, \dots\} \cup \cdotsWe enumerate them by r_{ij} for i, j \in \N. The idea is that r_{i0}, r_{i1}, \dots are a list of candidate witnesses to R_{i,A}, and R_{i,B}. • At stage 0, we initialize the algorithm by outputting A_0 := \emptyset, B_0 := \emptyset, and assigning witnesses to all requirements: • for R_{i,A}, assign witness w_{i,A} \leftarrow r_{i0}; • for R_{i,B}, assign witness w_{i,B} \leftarrow r_{i0}. • Note that, even though we are performing an infinite number of assignments, this can be done, because the entire assignment is computable. Later, we will update this infinite list of assignments. But we will ensure every update is still computable. • At stage 2n, • We check the health of all requirements R_{i,A} for all i\in 0:2n-1, by simulating TM_i^{B_{2n-1}}(w_{i,A}) for up to 2n-1 steps. • If all these TM_i^{B_{2n-1}}(w_{i,A}) \neq 0 at step 2n-1, either because it hasn't halted yet, or because it halted on a different value, then we have no positive evidence that we need to change anything. So we change nothing. Keep all witnesses the same, and outputA_{2n} := A_{2n-1}, B_{2n} := B_{2n-1} • Otherwise, find the lowest i such that TM_i^{B_{2n-1}}(w_{i,A}) =0. The requirement R_{i,A} is the priority injured requirement. • Output A_{2n} := A_{2n-1} \cup \{w_{i,A}\} to heal the priority injured requirement, and simultaneously update all w_{i,B}, w_{i+1,B}, \dots byw_{j,B} \leftarrow \min\{ r_{jk} : k \in \N, r_{jk} > \max(w_{j,B}, \phi_i^{B_{2n-1}}(w_{i,A}))\}to ensure that, if we ever need to heal one of the requirements R_{i,B}, R_{i+1,B} by adding a witness into B, it will not thereby injure R_{i,A}. Nothing else needs to change, so we output B_{2n} := B_{2n-1} and keep all other witnesses the same. • In order to compute the assignment, we simply need to apply all updates in sequence. It is as if applying a list of software patches, one patch after another. Since each update is computable, the whole witness assignment at this step is still computable. • At stage 2n+1, the construction goes over almost exactly the same way. • The only difference is that, if i is injured, then we must simultaneously update all w_{i\color{red}+1\color{black},A}, w_{i+2,A}, \dots. This avoids an infinite mutual injury loop between R_{i,A} and R_{i,B}. The construction ensures that R_{i,A} can only be injured by attempts to heal R_{0,B}, R_{1,B}, \dots, R_{i-1,B}, and R_{i,B} only by R_{0,A}, R_{1,A}, \dots, R_{i,A}. Variants The same idea allows us to construct variants or stronger versions of the Friedberg–Muchnik theorem. We say that A \subset \N is autoreducible for some Turing machine TM_i, iff for all k, • TM_i^{A \setminus\{k\}}(k) = 0 and k \not\in A, or • TM_i^{A \setminus\{k\}}(k) = 1 and k \in A. In other words, each k \in A question can be settled by TM_i that inquires an oracle that will answer all questions concerning j\in A, as long as j \neq k. We say A is not autoreducible iff it is not autoreducible for any TM_i. Then there exists an enumerable but not autoreducible set A. We construct it thus: • We ensure nonautoreducibility with an infinite list of requirements. Let R_{i} be the requirement that TM_i does not autoreduce A. • We ensure every requirement can only be injured finitely often, by well-ordering the requirements R_0 \prec R_1 \prec \cdots. • We ensure every requirement can be healed infinitely often, by assigning an infinite list of potential witnesses r_{i0} to each requirement R_i. We also ensure \{r_{i0} are mutually disjoint. The previous construction then works in the same way, because it is impossible for any requirement to cause self-injury. Given an infinite and enumerable set C, we can construct C \supset A_0 \supset A_1 \supset \cdots, such that A_0, A_1, \dots are enumerable, mutually irreducible, and every inclusion is sparse. We construct it by generalizing the previous construction: • We ensure mutual irreducibility with an infinite list of requirements. Let R_{ijk} be the requirement that TM_i^{A_j} does not decide A_k. Here, j\neq k. • We ensure every requirement can only be injured finitely often, by well-ordering the requirements. • Any computable well-ordering will work. For example, we can use the Cantor zig-zag function f: \N^3 \to \N, then define R_{ijk} \prec R_{i'j'k'} \iff f(i,j,k) . • We ensure every requirement can be healed infinitely often by assigning, for each i, j, k such that j \neq k, an infinite list of potential witnesses r_{ijk0} that may eventually be inserted A_k to witness R_{ijk}. For each k, the lists \{r_{ijk0} are mutually disjoint. • We ensure C \supset A_0 \supset A_1 \supset \cdots sparsely by an iterative process of sparsification and partition: • Enumerate an infinite list of ascending elements c_0. This is possible since C is infinite and enumerable. • At stage 0, sparsify the list to c_0, c_2, c_4, c_8, \dots. Call this list L_0. Then partition L_0 into a doubly-infinite list of lists \{r_{ij00} . • At stage 1, sparsify L_0 into L_1. Then partition L_1 into a doubly-infinite list of lists \{r_{ij10} . • And so on. Combining the above two constructions, we can make all A_0, A_1, \dots non-autoreducible as well. == Friedberg–Muchnik theorem below C ==

This shows that the order-structure of Turing degrees is quite complicated, even among enumerable sets. WLOG, we assume that C is enumerated as C_0 \subsetneq C_1 \subsetneq C_2 \subsetneq \cdots , each C_n being a finite set. Permit To prove the theorem, we define the concept of permission. Technically, this is the Yates permitting. There are other kids of permissions. Given two sequences of finite sets A_n \uparrow A, C_n \uparrow C, we say that \{C_n\}_{n \in \N} permits \{A_n\}_{n \in \N} iff \forall n, i \quad C_n \cap [0:i] = C \cap [0:i] \implies i \not\in A_{n+1} \setminus A_nA bit more generally, if f : \N \to \N, then we say that \{C_n\}_{n \in \N} f-permits \{A_n\}_{n \in \N} iff \forall n, i \quad C_n \cap [0:f(i)] = C \cap [0:f(i)] \implies i \not\in A_{n+1} \setminus A_n {{Math proof Given any i, the finite initial segment C\cap [0:f(i)] is a limit of a sequence of finite sets: C_n\cap [0:f(i)] \uparrow C\cap [0:f(i)], and it is a finite set. So, we construct a C-oracle Turing machine, which takes i as input, and outputs the smallest n such that the limit is reached: C_n\cap [0:f(i)] = C \cap [0:f(i)]. Then, given any i, compute the corresponding n. By the permitting condition, i \not\in A_{n+1} \setminus A_n, i \not\in A_{n+2} \setminus A_{n+1}, \dots, thus i \in A iff i \in A_n, which is decidable. }} Proof The requirements are still the same, with the same priority: R_{0,A}\prec R_{0,B} \prec R_{1,A} \prec R_{1,B} \prec \cdots . In the original construction for the Friedberg–Muchnik theorem, if it were true that every time we add a witness via A_{2n} := A_{2n-1} \cup \{w_{i,A}\}, we also have w_{i,A} \geq \min(C_{2n+2} \setminus C_{2n}) , then by the permitting lemma, A \leq_T C . Similarly for B \leq_T C . However, this is not true in general. In order to bypass the difficulty, we define 3 types of witnesses, 2 types of injuries, and 1 type of permissive moves, that a requirement can have. • Type 0 witness: (w_{i,A, 0}, -, -). This tentatively witnesses w_{i,A, 0} \not\in A and TM_i^B(w_{i,A, 0}) \neq 0. • Type 1 witness: (w_{i,A, 0}, w_{i,A, 1}, -). This tentatively witnesses w_{i,A, 0} \not\in A and TM_i^B(w_{i,A, 0}) \neq 0, and w_{i,A, 1} \not\in A and TM_i^B(w_{i,A, 1}) = 0. • Type 2 witness: (-,-,w_{i,A, 2}). This tentatively witnesses w_{i,A, 2} \in A and TM_i^B(w_{i,A, 2}) = 0. • Type 0 injury: Because a prior requirement has made a permitted move, this requirement's witness has possibly been invalidated. The witness updates into a type 0 witness. • Type 1 injury: Because of a previous update to B, or because the computation has finally halted, a type 0 witness has been invalidated, in that TM_i^{B_{2n}}(w_{i,A, 0}) =0. The witness updates into a type 1 witness. • Permitted move: Because w_{i,A,1} \geq \min(C_{2n+2} \setminus C_{2n}), the type 1 witness updates into a type 2 witness. At stage 2n, • We check if any type 1 witness is permitted to be moved into a type 2 witness. • If so, then let i be the smallest i such that w_{i,A,1} \geq \min(C_{2n+1} \setminus C_{2n}), and we perform the update:A_{2n+1} := A_{2n} \cup\{w_{i,A,1}\},\; w_{i,A} \leftarrow (-,-, w_{i,A,1})and simultaneously incur type 0 injury on all w_{i,B}, w_{i+1,B}, \dots by updating each tow_{j,B} \leftarrow (\min\{ r_{jk} : k \in \N, r_{jk} > \max(w_{j,B}, \phi_i^{B_{2n-1}}(w_{i,A}))\}, -, -) • Otherwise, we check for all type 1 injuries. • For each i\in 0:2n-1, such that w_{i,A} is a type 0 or type 1 witness, • Simulate TM_i^{B_{2n-1}}(w_{i,A,0}) for up to 2n-1 steps. • If TM_i^{B_{2n-1}}(w_{i,A,0})[2n-1] = 0, then a type 1 injury has occurred. Update the witness tow_{i,A} \leftarrow (\min\{ r_{ik} : k \in \N, r_{ik} > w_{i,A,0}\}, w_{i,A,0}, -) Similarly for stage (2n+1). To show that the construction works, we need to show that each requirement's witness can only change state a finite number of times, by induction on the requirements. By inductive hypothesis, since R_{0,A}, R_{0,B}, \dots, R_{n,A}, R_{n,B} would only change their witnesses a finite number of times, R_{n+1,A} can only be type-0 injured a finite number of times. Consequently, the only way R_{n+1,A} can change its witness is if it is type-1 injured an infinite number of times. Suppose this is the case, then its witness will eventually settle into an infinite process of being repeatedly type-1 injured, never permitted to move into a type 2 witness. Suppose this is the case, then let f(k) be w_{n+1,A,1} at stage 2k. By construction, f(k) is a function that is computable, non-decreasing, and because the witness is injured infinitely many times, \lim_k f(k) = \infty. By assumption, this witness will eventually be stuck forever as a type 1 witness, never permitted to move, sof(k) for all large enough k. However, if this is the case, then C is decidable, contradicting the original assumption that C is enumerable but undecidable. == Sacks's splitting theorem ==

We also have and == See also ==