Set Turing reducibility, oracle codes, and the Turing jump
DefinitionAutoformalisationSCI_OracleThis file packages Turing reducibility between sets of natural numbers and defines the Turing jump and its iterates, as used in Theorems A.3, A.4 and the degree remarks.
For , its oracle is the total characteristic function if and otherwise, viewed as a partial function. Then means is computable with oracle (Mathlib's RecursiveIn / TuringReducible), and means reducibility in both directions (equal Turing degree).
Oracle machines are represented by an inductive code type OracleCode whose constructors mirror those of Mathlib's Nat.RecursiveIn (zero, successor, the two unpair projections, the oracle, pairing, composition, primitive recursion, and unbounded search). OracleCode.eval B c is the partial function computed by code with oracle . The Turing jump is the halting set of these machines, encoded as a set of naturals via ; the iterates are and , so is the halting problem.
Formalization Note. The code type is given a Gödel numbering and an Encodable instance so that machines can be encoded as natural numbers. That OracleCode.eval B enumerates exactly the RecursiveIn {χ_B} partial functions is the expected universality lemma for solvers to prove.
import Mathlib.Computability.RecursiveIn
import Mathlib.Computability.TuringDegree
import Mathlib.Data.Nat.Pairing
open Encodable Part
namespace AutoformalisationSCI
open scoped Computability
noncomputable def setOracle (A : Set ℕ) : ℕ →. ℕ := by
classical
exact PFun.lift (fun n => if n ∈ A then 1 else 0)
def SetTuringReducible (A B : Set ℕ) : Prop := setOracle A ≤ᵀ setOracle B
def SetTuringEquivalent (A B : Set ℕ) : Prop := SetTuringReducible A B ∧ SetTuringReducible B A
inductive OracleCode : Type
| zero : OracleCode
| succ : OracleCode
| left : OracleCode
| right : OracleCode
| oracle : OracleCode
| pair : OracleCode → OracleCode → OracleCode
| comp : OracleCode → OracleCode → OracleCode
| prec : OracleCode → OracleCode → OracleCode
| rfind : OracleCode → OracleCode
noncomputable def OracleCode.eval (B : Set ℕ) : OracleCode → ℕ →. ℕ
| .zero => fun _ => 0
| .succ => Nat.succ
| .left => fun n => (Nat.unpair n).1
| .right => fun n => (Nat.unpair n).2
| .oracle => setOracle B
| .pair f h => fun n => (Nat.pair <$> eval B f n <*> eval B h n)
| .comp f h => fun n => eval B h n >>= eval B f
| .prec f h => fun p =>
let (a, n) := Nat.unpair p
n.rec (eval B f a) fun y IH => do
let i ← IH
eval B h (Nat.pair a (Nat.pair y i))
| .rfind f => fun a =>
Nat.rfind fun n => (fun m => m = 0) <$> eval B f (Nat.pair a n)
def OracleCode.toNat : OracleCode → ℕ
| .zero => Nat.pair 0 0
| .succ => Nat.pair 1 0
| .left => Nat.pair 2 0
| .right => Nat.pair 3 0
| .oracle => Nat.pair 4 0
| .pair a b => Nat.pair 5 (Nat.pair a.toNat b.toNat)
| .comp a b => Nat.pair 6 (Nat.pair a.toNat b.toNat)
| .prec a b => Nat.pair 7 (Nat.pair a.toNat b.toNat)
| .rfind a => Nat.pair 8 a.toNat
private theorem pair_inj {a b c d : ℕ} (h : Nat.pair a b = Nat.pair c d) : a = c ∧ b = d := by
have := congrArg Nat.unpair h
rw [Nat.unpair_pair, Nat.unpair_pair] at this
exact Prod.mk.inj this
theorem OracleCode.toNat_injective : Function.Injective OracleCode.toNat := by
have key : ∀ a b : OracleCode, a.toNat = b.toNat → a = b := by
intro a
induction a with
| zero => intro b h; cases b with
| zero => rfl
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| succ => intro b h; cases b with
| succ => rfl
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| left => intro b h; cases b with
| left => rfl
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| right => intro b h; cases b with
| right => rfl
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| oracle => intro b h; cases b with
| oracle => rfl
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| pair a₁ a₂ ih₁ ih₂ => intro b h; cases b with
| pair b₁ b₂ =>
have h₂ := pair_inj (pair_inj h).2
rw [ih₁ _ h₂.1, ih₂ _ h₂.2]
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| comp a₁ a₂ ih₁ ih₂ => intro b h; cases b with
| comp b₁ b₂ =>
have h₂ := pair_inj (pair_inj h).2
rw [ih₁ _ h₂.1, ih₂ _ h₂.2]
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| prec a₁ a₂ ih₁ ih₂ => intro b h; cases b with
| prec b₁ b₂ =>
have h₂ := pair_inj (pair_inj h).2
rw [ih₁ _ h₂.1, ih₂ _ h₂.2]
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
| rfind a ih => intro b h; cases b with
| rfind b₁ => rw [ih _ (pair_inj h).2]
| _ => have := congrArg Nat.unpair h; simp_all [OracleCode.toNat, Nat.unpair_pair]
exact key
noncomputable instance : Encodable OracleCode :=
Encodable.ofInj OracleCode.toNat OracleCode.toNat_injective
noncomputable def turingJump (B : Set ℕ) : Set ℕ :=
{p | ∃ c : OracleCode, Encodable.encode c = p.unpair.1 ∧ (OracleCode.eval B c p.unpair.2).Dom}
noncomputable def jumpIter : ℕ → Set ℕ
| 0 => ∅
| j + 1 => turingJump (jumpIter j)
end AutoformalisationSCIRead-back
What the Lean code literally says, in plain math · claude-opus-4-8
setOracle A is the total partial-function oracle if else (defined noncomputably using classical decidability of membership). SetTuringReducible A B asserts setOracle A ≤ᵀ setOracle B, i.e. RecursiveIn {setOracle B} (setOracle A). SetTuringEquivalent A B is the conjunction of reducibility in both directions. OracleCode is an inductive type with nine constructors: five nullary (zero, succ, left, right, oracle), three binary (pair, comp, prec), one unary (rfind). OracleCode.eval B maps each code to a partial function by the clauses mirroring Nat.RecursiveIn, with the oracle constructor returning setOracle B. OracleCode.toNat is a Gödel numbering using Nat.pair with constructor tags –; toNat_injective proves it injective; an Encodable OracleCode instance is built from it. turingJump B is the set of such that for some code , encode c = p.unpair.1 and (eval B c p.unpair.2).Dom. jumpIter 0 = ∅ and jumpIter (j+1) = turingJump (jumpIter j). No membership or halting is assumed decidable; all such definitions are noncomputable.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.