can simulate a universal Turing machine is called Turing complete.

An abstract version of the universal Turing machine is the universal function, a computable function that can be used to calculate any other computable function. The UTM theorem proves the existence of such a function.

Efficiency

Without loss of generality, the input of Turing machine can be assumed to be in the alphabet {0, 1}; any other

1.Previous
3.Next