Oracle programs exactly capture relative partial recursiveness
ProvedFriedbergMuchnik.oracle_programs_exactcomputability-theoryfriedberg-muchnikpriority-construction
Let be arbitrary partial functions. Let denote the partial function interpreted from an oracle program in the imported language. Then
The programs use oracle queries, successor, pairing projections, pairing, composition, primitive recursion, and minimization from zero. The constant-zero function is expressible within this language. Equality is equality of partial functions, including their domains; no totality assumption is imposed on or .
This equivalence connects explicit program requirements to Mathlib's RecursiveIn and hence to the mission's Turing-reducibility predicate.
Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik
theorem oracle_programs_exact (O f : ℕ →. ℕ) :
RecursiveIn {O} f ↔ ∃ c : Program, oracleEval O c = f := by sorry
end FriedbergMuchnik
Source
Formalization bridge for the oracle programs in 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=51; semantics follows Mathlib Nat.RecursiveIn and RecursiveIn.iff_nat, https://github.com/leanprover-community/mathlib4/blob/0df444a360eaa60ab8c11dca51a86af692955474/Mathlib/Computability/RecursiveIn.lean. Program-tree encoding is transported from Nat.Partrec.Code, https://github.com/leanprover-community/mathlib4/blob/0df444a360eaa60ab8c11dca51a86af692955474/Mathlib/Computability/PartrecCode.lean.