Private-witness diagonalization for incomparable enumerable sets
ID: private-witness-diagonalization-for-incomparable-enumerable-sets
To prevent a Turing functional from computing the indicator function of an enumerated set , reserve a permanently unique fresh witness . On observing a convergent computation with oracle use , enumerate into if the answer is zero; otherwise keep it out. Restrain subsequent lower-priority enumerations into below . Higher-priority actions may initialize this strategy and retire its witness, but witnesses are never reused. In a finite-injury priority construction, mathematical induction on priority shows that the final computation, if observed, remains correct as a computation from the final oracle and disagrees with at . If no computation is ever observed after the final initialization, the final oracle computation diverges, since any convergent computation uses only finitely many eventually stable oracle bits.
New to topics? Read the docs here!