Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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 space-S computation has a single-tape simulation in O(n+S(n)) space

Statement

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

Facts & Assumptions

Given: A fixed deterministic multitape machine M with SpaceM(n)=O(S(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]

Worst-case space counts the total number of tape cells ever visited during a halting computation, by Worst-case time and space complexity of a machine.

[L3]

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

[L4]

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

Proof

technique · direct
1.1

Use the standard simulator from [L1] that stores the k simulated tapes as marked blocks on one tape. On an input of length n, the first simulated tape block initially records the whole input word, contributing n cells up to a constant factor. Beyond that initial block, the simulator records only cells that the multitape computation has visited, together with only constant-size bookkeeping per recorded cell and a fixed number of delimiters depending on M. If the simulated computation has visited at most S(n) cells altogether, [L2] therefore bounds the one-tape encoding length by O(n+S(n)).

L1L2givenconstruct
2.1

Therefore there exists a constant cM such that every halting run of the simulator on an input of length n visits at most cM(n+S(n)+1) cells. By [L3], this is O(n+S(n)). Taking maxima over all length-n inputs gives SpaceSM(n)=O(n+S(n)).

L3step 1.1
3.1

The simulator still decides the same language as M, and step 2.1 places it in the deterministic single-tape space class described by [L4].

L4step 1.1step 2.1

Depends on

Used by

Dependency tree · two levels

8 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