Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passverified 2026-09-24 (gpt-6-sol)
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.

An eventually positive time bound yields the same-order space bound

Statement

Let M be a fixed k-tape machine that halts on every input, and let T:N→[0,∞) be eventually at least 1 at every length for which an input word exists. If Time⁡M(n)=O(T(n)), then Space⁡M(n)=O(T(n)).

Facts & Assumptions

Given: A fixed halting k-tape machine M and a bound T with Time⁡M(n)=O(T(n)), eventually T(n)≥1 on inhabited input lengths.

[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.

Proof

technique · direct
1.1L1given

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.

2.1L1L2step 1.1∎

If there are no length-n inputs, the revised convention in [L1] makes both worst-case values zero. At an inhabited length, applying step 1.1 to the worst halting run gives Space⁡M(n)≤k(Time⁡M(n)+1). For sufficiently large inhabited lengths the hypothesis T(n)≥1 absorbs the additive constant, and [L2] converts the time bound into Space⁡M(n)=O(T(n)).

Depends on

Used by

Dependency tree · two levels

5 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