Computability of membership in the explicit priority stages
ProvedFriedbergMuchnik.stage_membership_computablecomputability-theoryfriedberg-muchnikpriority-construction
For the fixed finite-stage construction in the imported definition bundle, let be the list of numbers enumerated on side by stage . The relation
is computable, uniformly in the stage, side, and natural-number input. All stages, including stage zero, are included.
The lists are produced by the specified least-requirement priority step and bounded oracle interpreter. This theorem supplies the effectiveness assertion needed to show their unions are c.e.; it makes no assumption that the construction's stages are computable.
Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik
theorem stage_membership_computable :
ComputablePred (fun p : ℕ × (Bool × ℕ) => p.2.2 ∈ stageList p.2.1 p.1) := 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=51, pp. 52–53, Construction and the assertion that the finite-stage sequence is recursive. This is the stage-membership consequence for the explicit syntax, bounded simulation, and list representation in FriedbergMuchnik.priorityStage.