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 halting oracle is not computably dominated
Statement
The ordinary halting oracle is not computably dominated.
Facts & Assumptions
Given: the halting oracle .
Its diagonal halting set and effective program syntax are specified in The Turing jump.
The empty oracle cannot compute its jump, by Every oracle is strictly below its jump.
Computable domination means that every total oracle-computable function has some total computable pointwise upper bound, by Computably dominated oracles.
Proof
With an oracle query to , define when diverges. Otherwise simulate that program, answering every empty-oracle query negatively, and let be its least halting stage, counted from its initial configuration. The query guarantees that this simulation terminates when it is undertaken. Thus is total and -computable.
If a total computable function satisfies for every , an ordinary machine decides as follows: compute , simulate through that many transitions (also checking the initial configuration), and answer yes exactly if it halts. Every halting computation is detected because its halting stage is at most ; every nonhalting computation is answered no. This would make computable from the empty oracle, contrary to [F2].
Therefore this particular total -computable function has no total computable pointwise upper bound. By [F3], is not computably dominated.
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
- Ludovic Patey, Computability Theory, Example 2.3 and §7.5 (standard reference, not scraped)