Friedberg–Muchnik theorem

In mathematical logic, the Friedberg–Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s.^[1]^[2] It is a more general view of the Kleene–Post theorem. The Kleene–Post theorem states that there exist incomparable languages A and B that are Turing reducible to the halting problem. The Friedberg–Muchnik theorem states that there exist incomparable, computably enumerable languages A and B. Incomparable meaning that there does not exist a Turing reduction from A to B or a Turing reduction from B to A. It is notable for its use of the priority finite injury approach.^[3]

Notation

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 \mathbb {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

Kleene–Post theorem—There exists two subsets $A,B\subset \mathbb {N}$ , such that $A<_{T}H,B<_{T}H,A\not <_{T}B,B\not <_{T}A$ . Here, $H$ is the halting oracle, i.e. the set of i such that the i-th Turing machine $TM_{i}$ halts on the empty input.

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$ $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:

Friedberg–Muchnik theorem—There exists two computationally enumerable subsets $A,B\subset \mathbb {N}$ , such that $A\not <_{T}B,B\not <_{T}A$ .

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$ $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 $\mathbb {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 \cdots$ We enumerate them by $r_{ij}$ for $i,j\in \mathbb {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$ $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 output $A_{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}\}$ $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$ $w_{i,B},w_{i+1,B},\dots$ by $w_{j,B}\leftarrow \min\{r_{jk}:k\in \mathbb {N} ,r_{jk}>\max(w_{j,B},\phi _{i}^{B_{2n-1}}(w_{i,A}))\}$ $w_{j,B}\leftarrow \min\{r_{jk}:k\in \mathbb {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}$ $R_{i,B},R_{i+1,B}$ by adding a witness into $B$ $B$ , it will not thereby injure $R_{i,A}$ $R_{i,A}$ . Nothing else needs to change, so we output $B_{2n}:=B_{2n-1}$ $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.^[4]

We say that $A\subset \mathbb {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}<r_{i1}<\cdots$ to each requirement $R_{i}$ . We also ensure $\{r_{i0}<r_{i1}<\cdots \}_{i\in \mathbb {N} }$ 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:\mathbb {N} ^{3}\to \mathbb {N}$ , then define $R_{ijk}\prec R_{i'j'k'}\iff f(i,j,k)<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}<r_{ijk1}<\cdots$ that may eventually be inserted $A_{k}$ to witness $R_{ijk}$ . For each $k$ , the lists $\{r_{ijk0}<r_{ijk1}<\cdots \}_{i\in \mathbb {N} ,j\in \mathbb {N} ,j\neq k}$ are mutually disjoint.
We ensure $C\supset A_{0}\supset A_{1}\supset \cdots$ $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}<c_{1}<\cdots \in C$ . 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}<r_{ij01}<\cdots \}_{i\in \mathbb {N} ,j\in \mathbb {N} ,j\neq 0}$ .
- At stage 1, sparsify $L_{0}$ into $L_{1}$ . Then partition $L_{1}$ into a doubly-infinite list of lists $\{r_{ij10}<r_{ij11}<\cdots \}_{i\in \mathbb {N} ,j\in \mathbb {N} ,j\neq 1}$ .
- 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

Friedberg–Muchnik theorem below $C$ —Given an enumerable but not computable $C$ , there exists enumerable sets $A,B\subset \mathbb {N}$ , such that $A\not <_{T}B,B\not <_{T}A,A<_{T}C,B<_{T}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 \mathbb {N} }$ permits $\{A_{n}\}_{n\in \mathbb {N} }$ iff $\forall n,i\quad C_{n}\cap [0:i]=C\cap [0:i]\implies i\not \in A_{n+1}\setminus A_{n}$ A bit more generally, if $f:\mathbb {N} \to \mathbb {N}$ , then we say that $\{C_{n}\}_{n\in \mathbb {N} }$ f-permits $\{A_{n}\}_{n\in \mathbb {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}$

Permitting lemma—Given enumerable sequences of finite sets $A_{n}\uparrow A,C_{n}\uparrow C$ , and a function $f:\mathbb {N} \to \mathbb {N}$ computable by a Turing machine equipped with $C$ -oracle, if $\{C_{n}\}_{n\in \mathbb {N} }$ f-permits $\{A_{n}\}_{n\in \mathbb {N} }$ , then $A\leq _{T}C$

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 to $w_{j,B}\leftarrow (\min\{r_{jk}:k\in \mathbb {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$ $i\in 0:2n-1$ , such that $w_{i,A}$ $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 to $w_{i,A}\leftarrow (\min\{r_{ik}:k\in \mathbb {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, so $f(k)<\min(C_{2k+2}\setminus C_{2k})$ 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^[5]

Sacks's splitting theorem—Given an enumerable but not computable $C$ , it can be partitioned into two enumerable sets $A,B\subset \mathbb {N}$ , such that $A\not <_{T}B,B\not <_{T}A$ .

and

Sacks's density theorem—The computably enumerable degrees are dense.

Friedberg–Muchnik theorem

Notation

Kleene–Post theorem

Friedberg–Muchnik theorem

Finite injury method

Proof

Variants

Friedberg–Muchnik theorem below C

Permit

Proof

Sacks's splitting theorem

See also

References

Related Articles

Timelines

Top Qs

Fact Checks