Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SCI hierarchy for decision problems via arithmetic towers

Definition
AutoformalisationSCI_SCI

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

computabilitymathematical-logicsci-hierarchy

This 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 N\mathbb NN and the output space is {0,1}\{0,1\}{0,1} with the discrete metric, so a sequence converges iff it is eventually constant. IterLimit h g b says the iterated limit lim⁡s1⋯lim⁡shg(s1,…,sh)\lim_{s_1}\cdots\lim_{s_h} g(s_1,\dots,s_h)lims1​​⋯limsh​​g(s1​,…,sh​) equals bbb, with every successive limit existing (for each fixed choice of the outer indices). A tower of height hhh for Ξ:N→{0,1}\Xi:\mathbb N\to\{0,1\}Ξ:N→{0,1} is a computable Γ:N×Nh→{0,1}\Gamma:\mathbb N\times\mathbb N^h\to\{0,1\}Γ:N×Nh→{0,1} whose iterated limit equals Ξ(e)\Xi(e)Ξ(e) for every eee; a height-zero tower is a computable function equal to Ξ\XiΞ. SCI_A Ξ is the least height of a tower for Ξ\XiΞ, and +∞+\infty+∞ (represented by ⊤ in WithTop ℕ) if no finite tower exists. DeltaA h Ξ expresses SCIA(Ξ)≤h\mathrm{SCI}_A(\Xi)\le hSCIA​(Ξ)≤h, i.e. Ξ∈Δh+1A\Xi\in\Delta^A_{h+1}Ξ∈Δh+1A​. setProblem A is the decision problem of a set A⊆NA\subseteq\mathbb NA⊆N.

Formalization Note. Nh\mathbb N^hNh is represented as Fin h → ℕ. The definition of SCI_A uses Nat.find on the (classically decidable) existence of a tower, hence is noncomputable.

Definition code
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 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. See also M. J. Colbrook, A. C. Hansen, JEMS 25(12) 2022, Definitions 5.2–5.6.
Read-back

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

IterLimit is defined by recursion on hhh: at 000, IterLimit 0 g b is g Fin.elim0 = b; at h+1h+1h+1, it is the conjunction of (i) for every s1s_1s1​ there exists b′b'b′ with IterLimit h (fun ss => g (Fin.cons s₁ ss)) b', and (ii) there exists NNN such that for all s1≥Ns_1\ge Ns1​≥N, IterLimit h (fun ss => g (Fin.cons s₁ ss)) b. IsTower Ξ h asserts the existence of a computable Γ:N×(Fin h→N)→Bool\Gamma:\mathbb N\times(\mathrm{Fin}\ h\to\mathbb N)\to\mathrm{Bool}Γ:N×(Fin h→N)→Bool such that for every eee, IterLimit h (fun ss => Γ (e, ss)) (Ξ e). SCI_A Ξ is (Nat.find h : WithTop ℕ) if a tower exists (with hhh the least height), else ⊤; it is noncomputable. DeltaA h Ξ is SCI_A Ξ ≤ (h : WithTop ℕ). setProblem A n is true if n∈An\in An∈A else false (noncomputable). Heights h=0h=0h=0 and empty/unbounded cases are included by the definitions.

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