TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

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 recursion theorem with parameters

Statement

Fix an acceptable numbering $(φ_{e})_{e \in N}$ . For every total computable function $F : N^{2} \to N,$ there exists a total computable function $q : N \to N$ such that for every parameter $a$ , $φ_{q (a)} = φ_{F (a, q (a))} .$

Facts & Assumptions

Given: A total computable function $F : N^{2} \to N$ .

[L1]

The $s$ -m- $n$ theorem gives a total computable specialization function $s_{2}^{1}$ , by The s-m-n theorem.

[L2]

Kleene's second recursion theorem gives fixed points for total computable program transformers, by Kleene's second recursion theorem.

Proof

technique · direct

1.1L1givenconstruct

Let $s_{2}^{1}$ be the specialization function from [L1]. Define a ternary partial computable function by $Ψ (a, u, x) : = φ_{F (a, s_{2}^{1} (u, a, u))} (x) .$ Because $F$ and $s_{2}^{1}$ are total computable, $Ψ$ is partial computable, so choose an index $r$ with $φ_{r} (⌜ a, ⌜ u, x ⌝_{s e q} ⌝_{s e q}) ≃ Ψ (a, u, x)$ for all $a, u, x$ .

2.1L1step 1.1construct

Define $q (a) : = s_{2}^{1} (r, a, r) .$ This function is total computable because $s_{2}^{1}$ is.

3.1L1step 2.1algebra

For every $a$ and $x$ , $φ_{q (a)} (x) ≃ φ_{r} (⌜ a, ⌜ r, x ⌝_{s e q} ⌝_{s e q}) = Ψ (a, r, x) = φ_{F (a, s_{2}^{1} (r, a, r))} (x) = φ_{F (a, q (a))} (x) .$ Hence $φ_{q (a)} = φ_{F (a, q (a))}$ for every parameter $a$ .

4.1L2step 3.1∎

Therefore the fixed-point construction can be carried out uniformly in the external parameter.

Depends on

Used by

Myhill's isomorphism theorem for creative sets Theorem

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

Robert I. Soare, Turing Computability: Theory and Applications (standard reference, not scraped)
Lawrence S. Moss, Invitation to Computability and Recursion, The Recursion Theorem (standard reference, not scraped)