Primitive recursiveness of bounded evaluation for finite-list oracles
ProvedFriedbergMuchnik.finite_oracle_evaln_primreccomputability-theoryfriedberg-muchnikoracle-computationprimitive-recursion
Let be an arbitrary finite list of natural numbers and let be when and otherwise. Let be the option-valued result of the fixed bounded oracle interpreter oracleEvaln, using oracle , fuel , program , and input .
Then the function
is primitive recursive, uniformly in all four arguments, with the existing encodings of lists, programs, products, and optional natural numbers. The result none is a legitimate total output of this bounded simulation.
The statement includes arbitrary lists, with duplicates allowed, fuel zero, and inputs beyond the fuel bound. It assumes no stage invariant, no computability of the priority construction, and no correctness or completeness theorem about unbounded oracle evaluation.
Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik
theorem finite_oracle_evaln_primrec :
Primrec (fun p : List ℕ × (ℕ × (Program × ℕ)) =>
oracleEvaln (fun n => if n ∈ p.1 then 1 else 0)
p.2.1 p.2.2.1 p.2.2.2) := by sorry
end FriedbergMuchnik
Source
Arnold W. Miller, Lecture notes in Recursion Theory, December 3, 2008, Section 26, Theorem 26.2, pp. 51–54, https://people.math.wisc.edu/~awmille1/old/m773-07/recthy.pdf#page=52. The construction on p. 52 uses a uniformly bounded finite-oracle simulation; p. 53 asserts effectiveness of the finite-stage sequence. This statement is an elementary, formalization-specific coding lemma for the oracleEvaln interpreter already defined in FriedbergMuchnik_Priority, not a verbatim numbered theorem in Miller. The strengthening to primitive recursiveness is justified by the explicit fuel and input bounds, primitive recursive syntax encoding, and bounded loops.