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.
Effective enumeration of clocked machines
Statement
Fix a total computable bound and one halting constructor for its values. There is a total effective decoding of binary strings into pairs , where is a deterministic multitape machine and is an integer. Every pair occurs and has arbitrarily long padded codes; malformed codes denote a fixed rejecting pair.
A decoded pair can be equipped either with a step clock or with a visited-cell cap . A step clock rejects on expiry. A cell cap rejects before the next visit would exceed the cap, but does not by itself force a looping computation to halt. The cap counts simulated cells, not the constructor's or simulator's own resource use. Resource-bounded applications must separately charge construction and simulation costs and impose their appropriate time- or space-constructibility hypotheses.
Facts & Assumptions
Given: the fixed and its constructor, and a finite binary string .
Proof
Parse into three self-delimiting fields for a machine code, a canonical positive binary integer , and an ignored padding string, rejecting trailing data. Use the finite-table multitape extension in An efficient universal simulation with a clock of the total decoder in A fixed effective binary encoding of deterministic one-tape Turing machines. Invalid fields return the fixed rejector pair with multiplier one. Every finite string is thereby decoded in finite time; listing all strings in length-lexicographic order gives the enumeration.
For each valid machine and multiplier, encoding these fields with successively longer padding supplies arbitrarily long codes for that pair. On input , compute using the fixed halting constructor. A step counter enforces simulated transitions, returning a halting result if it occurs within the budget and otherwise rejecting. This is the supplied step-clock interface.
For a cell cap, maintain the minimum and maximum visited position on each simulated tape, together with their total interval length. Each tape head moves to an adjacent cell, so these intervals count precisely its visited cells. Include the initial visited cells, rejecting immediately if they already exceed , and reject before a transition that would enlarge the total beyond . This effective monitor preserves every run staying within the cap; a loop inside it may continue forever. A separate configuration clock is needed to force such a run to halt.
If the relevant resource use of is , some fixed positive integer bounds it for all sufficiently large . The enumeration includes this pair, and its corresponding monitor then preserves those computations. No claim about exceptional small lengths where , or about the monitor's own resource overhead, is implicit.
Depends on
Used by
Dependency tree · two levels
6 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, Chapter 3 (standard reference, not scraped)