Enumeration and computation preservation for a permanent follower
ProvedFriedbergMuchnik.priority_permanent_follower_safetycomputability-theoryfriedberg-muchnikpriority-construction
Consider the fixed priority construction. Let and let be a Boolean flag. Assume that and that the entry for requirement at every stage is exactly the same pair . Put , let be the program with index , and write for the limit sets. Then
Moreover, if the permanent flag is true, there is a stage with
Here is the bounded oracle interpreter and is the characteristic function of the finite stage list. The result classifies a specified permanent follower and supplies a preserved finite computation for an acted flag. It does not assert existence of a permanent follower or correctness of unbounded oracle evaluation.
Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik
theorem priority_permanent_follower_safety (q a x : ℕ) (b : Bool)
(hqa : q < a)
(hstable : ∀ s : ℕ, a ≤ s →
(priorityStage s).2[q]?.getD (0, false) = (x, b)) :
(x ∈ limitSet (!(side q)) ↔ b = true) ∧
(b = true → ∃ t : ℕ, t < a ∧
oracleEvaln (stateOracle (priorityStage t) (side q)) t
(Denumerable.ofNat Program (q / 2)) x = some 0 ∧
∀ n : ℕ, n < t →
(n ∈ stageList (side q) t ↔ n ∈ limitSet (side q))) := 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. Verification cases (a) and (b) on pp. 53–54: distinct, unrepeated follower values and protection of the acted computation by appointing lower priority followers above its use. This conditional interface concerns the actual priorityStage entries and stageList unions. The activation hypothesis and stability of both follower and flag are explicit; prefix preservation uses the interpreter's bound on oracle queries. The combinatorial invariants are now proved directly in Lean: pairing-based follower freshness, monotone appointment stages, exact acted-flag membership, and preservation of the historical oracle prefix.