Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial log-cost RAM simulation of a binary list computation

Proved
TimeSpaceMA.widthListComputable_to_coinFreeRAM

by bersubs · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypseudorandomnessturing-machine

Let a deterministic polynomial-time multitape machine compute a finite list of naturals from a triple (n,k,v)(n,k,v)(n,k,v) using a unary width nnn and binary values for the other two fields. Then there is one coin-free log-cost RAM program PPP and an exponent eee such that for every n≥1n\ge1n≥1, k≤nk\le nk≤n, and v<2nv<2^nv<2n, starting PPP with [n,k,v][n,k,v][n,k,v] in memory halts with work at most ne+en^e+ene+e. At halt cell zero holds the list length and consecutive cells from address one hold the list entries.

This is the reverse machine-model transfer and output convention needed for a uniform neighbor listing. The unary width lets the source computation take polynomial time in nnn even for small numerical labels.

Preamble
import Definitions.Def_TimeSpaceMA_RAM
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_List
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Nat
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Pair
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Unary
Formal statement
namespace TimeSpaceMA

open Turing.MultiTapeTM

/-- Compile a polynomial-time binary list computation to the log-cost RAM's length and
consecutive-record output convention. The width is provided in unary to the source machine. Only valid width, entropy, and vertex triples need
be simulated within the width-based polynomial cost bound. -/
theorem widthListComputable_to_coinFreeRAM
    (listing : ℕ × ℕ × ℕ → List ℕ)
    (hlisting : ComputableInPolyTime listing (encPair encUnary (encPair encNat encNat))
      (encList encNat)) :
    ∃ (e : ℕ) (P : Program), P.CoinFree ∧
      ∀ n k v : ℕ, 1 ≤ n → k ≤ n → v < 2^n →
        ∃ st, P.RunsTo zeroTape (memOf [n,k,v]) st ∧ st.work ≤ n^e+e ∧
          st.mem 0 = (listing (n,k,v)).length ∧
          ∀ i : Fin (listing (n,k,v)).length, st.mem (1+i.val) = (listing (n,k,v))[i] := by sorry

end TimeSpaceMA
Source
Cook and Reckhow, Time Bounded Random Access Machines, JCSS 7 (1973), Theorem 2(b), https://www.cs.toronto.edu/~sacook/homepage/rams.pdf. Adapted to the published log-cost RAM, finite binary list I/O, and the polynomial bound in the width.

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