Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite injury: eventual stabilization and absence of attention

Proved
FriedbergMuchnik.priority_eventually_quiescent

by tomasz · Sep 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

computability-theoryfriedberg-muchnikpriority-construction

For the fixed priority construction, let Es(q)E_s(q)Es​(q) be the follower and acted flag stored for requirement qqq at stage sss. Let Ws(p)W_s(p)Ws​(p) be the Boolean test that requirement ppp requests attention at that stage. For every priority index q∈Nq\in\mathbb Nq∈N, there is a stage after activation such that

∃a>q  ∀s≥a,Es(q)=Ea(q)∧∀p≤q, Ws(p)=false.\exists a>q\;\forall s\ge a,\qquad E_s(q)=E_a(q)\quad\land\quad \forall p\le q,\ W_s(p)=\mathrm{false}.∃a>q∀s≥a,Es​(q)=Ea​(q)∧∀p≤q, Ws​(p)=false.

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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me