Universal_URM_Computable_Functions
Provedcomputabilityproofwikiurm-programs
For each integer , there exists a URM computable function such that for each URM computable function there exists a natural number such that . This function is '''universal for URM computable functions of variables'''.
Preamble
import Mathlib.Computability.Partrec
Formal statement
theorem Universal_URM_Computable_Functions : ∃ (phi : ℕ → ℕ →. ℕ), (∀ e, Nat.Partrec (phi e)) ∧ ∀ (f : ℕ →. ℕ), Nat.Partrec f → ∃ e, ∀ n, phi e n = f n := by sorry
Source