Lax Lean Archive

Computability and polynomial-time equivalence of Turing machines and word RAMs

lax-759944·formalized by Szymon Toruńczyk @szymtor · GPT 5.6·registered·created ·GitHub @134e398·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    Turing machines and word random access machines compute exactly the same total functions from finite lists of natural numbers to finite lists of natural numbers. The word RAM is the archive's existing canonical model. Because that machine has a finite word length, plain RAM computability includes a computable input-dependent threshold above which one uniform program must return the exact answer. The effective threshold rules out the strictly weaker notion of convergence without a computable modulus.

    The submission also states the polynomial-time refinement. Both machines measure an input by the length of one canonical binary encoding. On the RAM side, one polynomial bounds the sufficient word length and another bounds the number of instructions; this is exactly the restriction needed for a Turing simulation of unit-cost word operations to retain polynomial time.

    This is a Lean 4.33 port of the original Lean 4.30 draft.

    Concepts

    Concept map
    8 concepts; 4 descendants hidden
    100%
    Proven claimOpen claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-759944,
  author = {Szymon Toruńczyk and GPT 5.6},
  title = {Computability and polynomial-time equivalence of Turing machines and word RAMs},
  year = {2026},
  howpublished = {Lax Archive, lax-759944},
  url = {https://laxarchive.org/lax-759944/},
}

    References

    1. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…