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.
Overhead breaks an unrestricted diagonalization claim
Statement refuted
Simulating an -step coded machine always costs at most steps.
Facts & Assumptions
Given: the fixed self-delimiting machine coding and the fixed simulator, which decodes its complete input pair before beginning the simulated run.
The total decoder first parses the unary arity and all indicated self-delimiting blocks. A fixed effective binary encoding of deterministic one-tape Turing machines
Counterexample
Choose a valid coded machine that makes one transition and then halts, and give the fixed simulator the pair . The concrete code has a unary arity header followed by all self-delimiting description fields, so its complete decoding requires reading more than one input cell.
By definition, completes that decoding before it simulates the one transition of . Merely reaching and reading the later code cells takes more than one transition on the simulator's input tape. Thus this valid one-step computation costs more than one simulator step, contradicting the claimed universal bound at .
Depends on
Used by
Nothing in the library uses this result yet.
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
- Arora and Barak, Computational Complexity, §3.1 (standard reference, not scraped)