|
|
|
|
|
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... |
|