Octocurious

Home

❯

Universal program

Universal program

23 Jul 20261 min read

In computability theory, a universal program is a partial computable function U:N⇀N such that, for every program index e and input x,
U⟨e,x⟩≃ϕe​(x)
where ϕe​:N⇀N is a computable denumeration of partial recursive functions, and ⟨,⟩:N→N→N is a (computable) pairwise encoding of naturals.

References

cutland1980-computability


Graph View

Backlinks

  • Computable Denumeration
  • Kleene's Normal Form Theorem

Created with Quartz v4.5.2 © 2026

  • GitHub
  • Discord Community