LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-06

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.

An oracle computation has a finite query witness

Statement

If an oracle machine $M^{X} (x)$ halts, there is a finite set $F$ of queries such that every oracle $Y$ agreeing with $X$ on $F$ gives the same halting run and output on $x$ .

Facts & Assumptions

Given: a halting run of $M^{X}$ on $x$ .

Proof

technique · direct

1.1

The run has finitely many steps, hence performs only finitely many query instructions. Let $F$ be the set of numbers queried in that run.

givenconstruct

2.1

If $Y$ agrees with $X$ on $F$ , induction over those finitely many transitions gives the same state, tapes, query answers, and next transition at every step. Thus the run halts with the same output.

step 1.1induction∎

Depends on

Relative computability and relative enumerability

Used by

Post's theorem Theorem
Shoenfield's limit lemma Theorem

Dependency tree · one level

1 result within one dependency step 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, §4.4 (standard reference, not scraped)