patternMajor
What does being Turing complete mean?
Viewed 0 times
whatmeanbeingcompletedoesturing
Problem
I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get:
A computer is Turing complete if it can solve any problem that a Turing machine can...
While it is very well defined whether different systems are Turing complete or not, I haven't seen an explanation of what the implications/consequences of being Turing complete are.
What can a Turing machine do that where no non-Turing machine exists that can also perform the same task? For example a computer can perform simple calculations like
Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?
A computer is Turing complete if it can solve any problem that a Turing machine can...
While it is very well defined whether different systems are Turing complete or not, I haven't seen an explanation of what the implications/consequences of being Turing complete are.
What can a Turing machine do that where no non-Turing machine exists that can also perform the same task? For example a computer can perform simple calculations like
(1+5)/3=?, but an ordinary calculator can also do them, which is non-Turing complete if I am correct.Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?
Solution
It's not tautological at all.
A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines.
One thing that Turing machines can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can't do at least one thing that Turing machines can do, so it doesn't satisfy the definition, so it isn't Turing complete. There's no circularity because we didn't define Turing-completeness in terms of itself: we said that Turing-completeness is the property of being able to do everything that Turing machines can.
But there are plenty of other things that models of computation might fail to do. For example, no deterministic finite automaton (DFA) can recognize the class of strings consisting of some number of $a$s followed by the same number of $b$s. Turing machines, on the other hand, can recognize that class of strings. Hence, DFAs are not Turing-complete.
Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?
I'm not sure what you mean by "define the capabilities of Turing machines". The capabilities are defined in terms of the finite state automaton operating on the infinite tape. (I'll not repeat the full definition but you can find it, e.g., on Wikipedia.)
A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines.
One thing that Turing machines can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can't do at least one thing that Turing machines can do, so it doesn't satisfy the definition, so it isn't Turing complete. There's no circularity because we didn't define Turing-completeness in terms of itself: we said that Turing-completeness is the property of being able to do everything that Turing machines can.
But there are plenty of other things that models of computation might fail to do. For example, no deterministic finite automaton (DFA) can recognize the class of strings consisting of some number of $a$s followed by the same number of $b$s. Turing machines, on the other hand, can recognize that class of strings. Hence, DFAs are not Turing-complete.
Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?
I'm not sure what you mean by "define the capabilities of Turing machines". The capabilities are defined in terms of the finite state automaton operating on the infinite tape. (I'll not repeat the full definition but you can find it, e.g., on Wikipedia.)
Context
StackExchange Computer Science Q#71473, answer score: 39
Revisions (0)
No revisions yet.