Universal_URM_Programs
Provedcomputabilityproofwikiurm-programs
For each integer , there exists a URM program such that For each URM program there exists a natural number such that For all , the computation using the program with input has the same output as the computation using the program with input . This function is a '''universal program for URM computations with inputs'''.
Preamble
import Mathlib.Computability.Partrec
Formal statement
theorem Universal_URM_Programs : ∃ (phi : ℕ → ℕ →. ℕ), (∀ e, Nat.Partrec (phi e)) ∧ ∀ (f : ℕ →. ℕ), Nat.Partrec f → ∃ e, ∀ n, phi e n = f n := by sorry
Source