Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 120 / 5

A many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine which, with membership oracle $B$, halts on every input and computes the indicator function ${\chi }_A$. It may make finitely many adaptive queries on each input. A many-one reduction gives a Turing reduction by a single query, but Turing reducibility allows more general procedures.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Effectively enumerate all Turing functionals $({\Phi }_e)$. Arrange the requirements in the priority orderEquality would require the Turing functional to be total and give the correct bit at every input; one disagreement or one undefined input defeats it.

Start with $A_0=B_0=\varnothing$ and enumerate elements without ever removing them. A strategy has a private witness, a flag recording whether it has acted, and a restraint on its oracle. Every new witness is larger than every previously assigned witness and every current higher-priority restraint. Retired witnesses are never reused. The only possible enumeration of a witness is by its owner, so an unacted witness remains outside its target set.

The strategy for $R_e$ chooses a witness $x$ and waits for a stage at which the bounded simulation givesOn seeing this, put $x$ into $B$, declare the strategy acted, and impose restraint $u$ on $A$, where $u$ is the oracle use: one more than the largest queried number, or zero if there were no queries. Initialize every lower-priority strategy, discarding its current witness, acted flag and restraint. An acted strategy does nothing further until initialized. The strategy for $S_e$ is identical with $A,B$ interchanged. Waiting specifically for zero is enough: if the eventual output is nonzero while the witness stays out, it already disagrees with the target indicator function.

For a completely effective schedule, at stage $s$ visit the first $s+1$ strategies in priority order. Assign an unassigned witness when visited. Simulate each unacted strategy's computation for at most $s$ steps with the current finite oracle. If some strategy can act, perform the first such action and end the stage; otherwise end after all visits. All steps are finite and algorithmic, so the limiting $A,B$ are computably enumerable sets.

Every lower-priority enumeration respects higher-priority restraints. When its witness was chosen it lay above these restraints. Any subsequent action of a higher-priority strategy would have initialized it, so its current witness remains safe to enumerate. The initialization of all lower strategies also removes their obsolete restraints before they can obstruct a legitimate higher-priority action.

We verify finite injury by mathematical induction on priority. The first strategy is never injured and acts at most once. If all predecessors of a strategy act finitely often, there is a last stage when a higher-priority action initializes it. It is subsequently visited, chooses its permanent witness, and acts at most once. Thus it too acts finitely often and all its lower-priority strategies suffer only finitely many injuries. The scheduling cannot starve a fixed strategy: after the finitely many higher-priority actions, all sufficiently large stages visit it.

Consider the final uninjured $R_e$ with witness $x$. If it acts, then $x\in B$ permanently, and every later lower-priority enumeration into $A$ respects its restraint. No later higher-priority action occurs. The preserved computation is thereforeIf it never acts, $x\notin B$. Were ${\Phi }_e^A={\chi }_B$, the final computation on $x$ would halt with zero and have finite oracle use. The finitely many oracle bits it queries eventually stabilize, and a sufficiently late bounded stage simulation would see exactly this zero computation. The strategy would then act, a contradiction. Hence $R_e$ holds in this case too. The same reasoning proves every $S_e$.

All possible Turing reductions in both directions are excluded. This proves the Friedberg–Muchnik theorem; in particular both constructed Turing degrees are noncomputable, since a computable set is Turing reducible to every oracle.