Function_Obtained_by_Minimization_from_URM_Computable_Relations
Provedcomputabilityproofwikiurm-programs
Let be a URM computable -ary relation on . Let the function be a URM computable function. Let be the function obtained by minimization from thus Then is also URM computable.
Preamble
import Mathlib.Computability.Partrec
Formal statement
theorem Function_Obtained_by_Minimization_from_URM_Computable_Relations (R : ℕ → ℕ → Bool) (hR : Computable₂ R) : Nat.Partrec (fun n => Nat.rfind (fun m => some (R n m))) := by sorry
Source