4 ms·

First off, I admit I didn’t do my homework so I have no idea what I’m talking about, but couldn’t the Turing machine make a Turing machine interpreter and there

• tromp 6y 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#Universality https://tromp.github.io/cl/Binary_lambda_calculus.html#Unive...