Hacker News new | ask | show | jobs
by tromp 2210 days ago
There's different notions of universality.

In the more abstract one, you can emulate arbitrary computation by preparing the system (in case of the 2 state 3 symbol TM, its tape) in an appropriate configuration, letting it run until some the configuration satisfies some condition, and then extracting the result from the final configuration.

In a more concrete one, you have a language of programs, and a universal program takes a program description as input, and interprets it. I give a slightly more formal definition of such a notion of universality, as applicable to Algorithmic Information Theory, in [1].

[1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Unive...