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 satisfy and . Assume is space constructible: some fixed deterministic machine on halts with the binary numeral of using 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 can be made total in space as follows: run the fixed universal simulator of Space-bounded universal simulation with its entire encoded simulation workspace capped at , 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 , its fixed constructor, and the capped universal simulator from Space-bounded universal simulation.
Proof
Determine , form , and run the constructor to obtain . This halts and uses 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 cells for a fixed integer , by the simulator's cap interface. The integer itself can be computed in space.
Let 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 , and each tape can be represented by its first symbols; all later input symbols are fixed and all later work symbols are blank. Thus it has at most configurations. Since and , fix an integer large enough that this number is strictly below for every . All these constants belong to the fixed simulator, independently of the decoded adversary.
Simulate at most transitions of that capped simulator, checking halting or a cap abort at every stage. A binary counter of 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.
The constructor halts by hypothesis, and the later clock forces termination. Its counter uses 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
- Arora and Barak, Computational Complexity, §3.2 and §4.1 (standard reference, not scraped)