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 universal Turing machine exists for the chosen coding
Statement
There exists a deterministic one-tape Turing machine universal for the coding fixed in A universal Turing machine relative to a fixed machine encoding.
Facts & Assumptions
Given: The coding and pairing conventions fixed in A universal Turing machine relative to a fixed machine encoding.
A universal machine for the chosen coding is one that reproduces the halting outputs and divergence of every coded machine on every coded input pair, by A universal Turing machine relative to a fixed machine encoding.
Computing a partial function means matching halting outputs on the domain and divergence off the domain under the chosen encodings, by Partial functions computed by a machine under fixed encodings.
There is a deterministic machine that executes one encoded step of a coded machine and returns the same code unchanged in the halting case, by A fixed interpreter can execute one encoded machine step.
Every deterministic multitape Turing machine has an equivalent deterministic one-tape simulation, by Every fixed multitape Turing machine has an equivalent one-tape simulation.
Proof
Build a deterministic multitape machine that, on input , first decodes the coded machine from the first component and the input word from the second component block-by-block. It then copies to one work tape, constructs the encoded initial configuration of on input on a second work tape, and reserves a third work tape for running the one-step interpreter from [L3].
The machine now iterates the interpreter from [L3]. Before each cycle it checks whether the current code represents an accepting or rejecting configuration and stops the iteration if so; otherwise it replaces that code by the one-step successor returned by the interpreter. This state check, rather than equality of successive codes, detects halting.
Induction on the number of interpreter cycles shows that the maintained configuration code is always the code of the current configuration of on input . Therefore, if halts with output , then eventually reaches the halting configuration code, decodes the represented output word , writes its binary code in its own output convention, and halts. If diverges, the iteration never reaches a halting configuration code, so diverges as well. Thus has exactly the behavior required by [L1] and [L2].
Finally, [L4] converts the deterministic multitape interpreter into an equivalent deterministic one-tape machine. By step 3.1, that one-tape machine is universal for the chosen coding.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
9 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
- A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (standard reference, not scraped)
- Richard Zach, Sets, Logic, Computation: An Open Introduction to Metalogic (standard reference, not scraped)