Alphabeta Math
LemmaStatement: 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.

A time bound always yields the same-order space bound

Statement

Let M be a fixed k-tape machine that halts on every input. If TimeM(n)=O(T(n)), then SpaceM(n)=O(T(n)).

Facts & Assumptions

Given: A fixed halting k-tape machine M and a bound T with TimeM(n)=O(T(n)).

[L1]

Worst-case time and space count machine steps and visited tape cells, respectively, by Worst-case time and space complexity of a machine.

[L2]

Big-O means eventual domination up to a constant factor, by Asymptotic comparison of resource bounds.

[L3]

A machine that must inspect all n input cells needs at least linear time, by Any machine that fully reads every input of length n needs at least linear time.

Proof

technique · direct
1.1

During one step, each of the k heads can enter at most one new cell on its own tape. Therefore after t steps, the total number of visited cells across all tapes is at most the initial k cells plus kt. By [L1], every halting computation using t steps uses at most k(t+1) space.

L1given
2.1

Applying step 1.1 to the worst halting run on an input of length n gives SpaceM(n)k(TimeM(n)+1). The additive constant is harmless asymptotically, and [L2] converts this inequality together with the hypothesis TimeM(n)=O(T(n)) into SpaceM(n)=O(T(n)). When an argument also requires the budget to dominate input reading, [L3] supplies the usual linear lower bound.

L2L3step 1.1

Depends on

Used by

Dependency tree · two levels

6 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