Finite injury: eventual stabilization and absence of attention
ProvedFriedbergMuchnik.priority_eventually_quiescentcomputability-theoryfriedberg-muchnikpriority-construction
For the fixed priority construction, let be the follower and acted flag stored for requirement at stage . Let be the Boolean test that requirement requests attention at that stage. For every priority index , there is a stage after activation such that
Thus both the follower and its acted flag stabilize, and every requirement of higher or equal priority eventually stops requesting attention. The statement concerns the explicit scheduler and makes no assumption about correctness of its oracle simulations. It supplies the finite injury part of the verification independently of diagonalization.
Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik
theorem priority_eventually_quiescent (q : ℕ) :
∃ a : ℕ, q < a ∧ ∀ s : ℕ, a ≤ s →
(priorityStage s).2[q]?.getD (0, false) =
(priorityStage a).2[q]?.getD (0, false) ∧
∀ p : ℕ, p ≤ q → wantsAttention s (priorityStage s) p = false := 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. The verification on pp. 53–54, Claim (1) and (3), and the induction on priority. This interface states stabilization of the complete entry and eventual absence of attention, as obtained from the least-attention scheduler and acted flags in the existing priorityStage implementation. An accompanying direct Lean proof checks this strengthening from the update rule.