Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passverified 2026-09-08 (gpt-6-astra)
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.

The space-diagonal machine halts

Statement

Let s:N→N satisfy s(n)≥1 and n=O(s(n)). Assume s is space constructible: some fixed deterministic machine on 1n halts with the binary numeral of s(n) using O(s(n)) all-tapes space. Here resource bounds have the meaning of The classes DTIME, NTIME, DSPACE, and NSPACE.

An all-tapes diagonal procedure on a coded description/input of length n can be made total in O(s(n)) space as follows: run the fixed universal simulator of Space-bounded universal simulation with its entire encoded simulation workspace capped at s(n), and stop it after a configuration bound for that fixed capped simulator. If the simulated machine halts without a cap abort, its answer is seen before this timeout. On an abort, malformed input, or timeout give a fixed default answer; on a simulated halting answer the diagonal procedure may invert that answer.

The cap is on the fixed simulator's encoded configuration and scratch, not on raw symbols of a variable-alphabet machine.

Facts & Assumptions

Given: the function s, its fixed constructor, and the capped universal simulator from Space-bounded universal simulation.

Proof

1.1givenconstruct

Determine n, form 1n, and run the constructor to obtain B=s(n). This halts and uses O(n+s(n))=O(s(n)) space. Thereafter use the fixed capped simulator, excluding the timeout counter for now. Its coded input and binary bound, cap bookkeeping, representation, and scratch fit in K=C(n+B+1) cells for a fixed integer C, by the simulator's cap interface. The integer K itself can be computed in O(n+B+1) space.

2.1step 1.1algebra

Let q,k,a be respectively the number of states, tapes, and tape symbols of this fixed capped simulator. On its fixed input, each head is in a position below K+1, and each tape can be represented by its first K+1 symbols; all later input symbols are fixed and all later work symbols are blank. Thus it has at most q(K+1)kak(K+1) configurations. Since K≥1 and K+1≤2K, fix an integer d large enough that this number is strictly below 2dK for every K≥1. All these constants belong to the fixed simulator, independently of the decoded adversary.

3.1step 2.1construct

Simulate at most 2dK transitions of that capped simulator, checking halting or a cap abort at every stage. A binary counter of dK+1 bits suffices. If a deterministic computation repeats a configuration, its future repeats and it cannot first halt later. Consequently any halting capped computation halts before this clock expires; otherwise the procedure returns its default answer. This counts transitions of the fixed simulator itself, including its scans and scratch updates, rather than transitions of the decoded machine.

4.1step 1.1step 3.1algebra∎

The constructor halts by hypothesis, and the later clock forces termination. Its counter uses O(K)=O(n+s(n))=O(s(n)) cells, as do the capped simulation and retained input. Therefore the resulting diagonal procedure is total in the asserted space, preserving every non-aborted simulated halting answer for inversion.

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