SCI hierarchy for decision problems via arithmetic towers
DefinitionAutoformalisationSCI_SCIThis file defines the Solvability Complexity Index (SCI) for decision problems via arithmetic (computable) towers, as in Appendix A.2 of the paper.
The input space is and the output space is with the discrete metric, so a sequence converges iff it is eventually constant. IterLimit h g b says the iterated limit equals , with every successive limit existing (for each fixed choice of the outer indices). A tower of height for is a computable whose iterated limit equals for every ; a height-zero tower is a computable function equal to . SCI_A Ξ is the least height of a tower for , and (represented by ⊤ in WithTop ℕ) if no finite tower exists. DeltaA h Ξ expresses , i.e. . setProblem A is the decision problem of a set .
Formalization Note. is represented as Fin h → ℕ. The definition of SCI_A uses Nat.find on the (classically decidable) existence of a tower, hence is noncomputable.
import Mathlib.Computability.Partrec
import Mathlib.Data.ENat.Basic
open Encodable
open scoped Classical
namespace AutoformalisationSCI
def IterLimit : (h : ℕ) → ((Fin h → ℕ) → Bool) → Bool → Prop
| 0, g, b => g Fin.elim0 = b
| h + 1, g, b =>
(∀ s₁, ∃ b', IterLimit h (fun ss => g (Fin.cons s₁ ss)) b') ∧
(∃ N, ∀ s₁ ≥ N, IterLimit h (fun ss => g (Fin.cons s₁ ss)) b)
def IsTower (Ξ : ℕ → Bool) (h : ℕ) : Prop :=
∃ Γ : ℕ × (Fin h → ℕ) → Bool, Computable Γ ∧ ∀ e, IterLimit h (fun ss => Γ (e, ss)) (Ξ e)
noncomputable def SCI_A (Ξ : ℕ → Bool) : WithTop ℕ :=
if h : ∃ h : ℕ, IsTower Ξ h then (Nat.find h : WithTop ℕ) else ⊤
def DeltaA (h : ℕ) (Ξ : ℕ → Bool) : Prop := SCI_A Ξ ≤ (h : WithTop ℕ)
noncomputable def setProblem (A : Set ℕ) : ℕ → Bool := fun n => if n ∈ A then true else false
end AutoformalisationSCIRead-back
What the Lean code literally says, in plain math · claude-opus-4-8
IterLimit is defined by recursion on : at , IterLimit 0 g b is g Fin.elim0 = b; at , it is the conjunction of (i) for every there exists with IterLimit h (fun ss => g (Fin.cons s₁ ss)) b', and (ii) there exists such that for all , IterLimit h (fun ss => g (Fin.cons s₁ ss)) b. IsTower Ξ h asserts the existence of a computable such that for every , IterLimit h (fun ss => Γ (e, ss)) (Ξ e). SCI_A Ξ is (Nat.find h : WithTop ℕ) if a tower exists (with the least height), else ⊤; it is noncomputable. DeltaA h Ξ is SCI_A Ξ ≤ (h : WithTop ℕ). setProblem A n is true if else false (noncomputable). Heights and empty/unbounded cases are included by the definitions.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.