Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Set Turing reducibility, oracle codes, and the Turing jump

Definition
AutoformalisationSCI_Oracle

by LG · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitymathematical-logicturing-degrees

This 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 A⊆NA\subseteq\mathbb NA⊆N, its oracle is the total characteristic function χA(n)=1\chi_A(n)=1χA​(n)=1 if n∈An\in An∈A and 000 otherwise, viewed as a partial function. Then A≤TBA\le_T BA≤T​B means χA\chi_AχA​ is computable with oracle χB\chi_BχB​ (Mathlib's RecursiveIn / TuringReducible), and A≡TBA\equiv_T BA≡T​B 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 ccc with oracle BBB. The Turing jump B′B'B′ is the halting set of these machines, encoded as a set of naturals via ⟨code,input⟩\langle\text{code},\text{input}\rangle⟨code,input⟩; the iterates are ∅(0)=∅\emptyset^{(0)}=\emptyset∅(0)=∅ and ∅(j+1)=(∅(j))′\emptyset^{(j+1)}=(\emptyset^{(j)})'∅(j+1)=(∅(j))′, so ∅(1)\emptyset^{(1)}∅(1) 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.

Definition code
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 AutoformalisationSCI
Source
A. Bastounis, F. Circelli, A. C. Hansen, Navier–Stokes lost in translation, arXiv:2610.08144 (2026), Appendix A (pp. 17–23); https://arxiv.org/abs/2610.08144. Standard background: R. I. Soare, Turing Computability, Springer 2016, Ch. 4.
Read-back

What the Lean code literally says, in plain math · claude-opus-4-8

setOracle A is the total partial-function oracle n↦1n\mapsto 1n↦1 if n∈An\in An∈A else 000 (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 N⇀N\mathbb N\rightharpoonup\mathbb NN⇀N 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 000–888; toNat_injective proves it injective; an Encodable OracleCode instance is built from it. turingJump B is the set of ppp such that for some code ccc, 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.

Human review
  • Endorsed by Shuze Chen · Nov 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me