Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Every multitape time-T computation has a single-tape simulation in O((n+T(n))^2) time

Statement

Let M be a fixed deterministic multitape Turing machine. If TimeM(n)=O(T(n)), then there exists a deterministic one-tape Turing machine SM deciding the same language and satisfying TimeSM(n)=O((n+T(n))2).

Facts & Assumptions

Given: A fixed deterministic multitape machine M with TimeM(n)=O(T(n)).

[L1]

Every fixed multitape machine has an equivalent deterministic one-tape simulator, by Every fixed multitape Turing machine has an equivalent one-tape simulation.

[L2]

On an input w, if the fixed multitape machine runs for t steps, the standard simulator runs for at most cM(w+t+1)2 steps, by The standard one-tape simulation of a fixed multitape machine has quadratic overhead.

[L3]

Big-O compares functions up to eventual constant factors, by Asymptotic comparison of resource bounds.

[L4]

The class notation DTIME records deterministic decision procedures within an asymptotic time bound, by The classes DTIME, NTIME, DSPACE, and NSPACE.

Proof

technique · direct
1.1

By [L1], choose the one-tape simulator SM that reproduces the accept, reject, and divergence behavior of M on every input.

L1givenconstruct
2.1

For an input w of length n, let t=timeM(w). The quadratic-overhead lemma [L2] gives timeSM(w)cM(w+t+1)2 for a constant cM depending only on M. Because tTimeM(n) and w=n, the hypothesis and [L3] imply timeSM(w)=O((n+T(n))2). Taking the maximum over all w of length n yields TimeSM(n)=O((n+T(n))2).

L2L3step 1.1
3.1

The simulator from step 1.1 decides the same language as M, and step 2.1 gives the quantitative bound. Therefore the language decided by M also lies in the one-tape deterministic time class described by [L4].

L4step 1.1step 2.1

Depends on

Used by

Dependency tree · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources