Problem Detail: I’m a bit confused about these concepts. As far as I understand, something is Turing complete when it can simulate a Turing machine. And there is this thing called a Universal Turing machine which is universal because it can simulate a Turing machine. Which to me, implies there are Turing machines that are not universal and cannot simulate a Turing machine. Does this mean non-universal Turing machines are not Turing complete? Could anyone clarify this concepts for me?
Asked By : Juan
Answered By : Luke Mathieson
In short yes, a non-universal Turing Machine is not Turing-complete. The key part is that a computational model is Turing-complete if it can simulate any Turing Machine (or using the transitivity of the simulations, if it can simulate a Universal Turing Machine). As you note, many Turing Machines are not Universal, they compute something, but they can’t simulate any computation that any Turing Machine could do. A possibly intuitive practical way of thinking about this is that Turing Machines are normally equivalent to programs – they take a particular type of input and compute some output. Universal Turing Machines are equivalent to programming languages or computers – you can build/run any program/Turing Machine on them. Of course I’m using “equivalent” very loosely here.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14691
