What does being Turing complete mean?

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 (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”?

Answer

I pondered a while whether to add yet another answer. The other answers focus on the middle of his question (about “turing complete”, “tautology” and so on). Let me grab the first and last part, and thus the bigger and slightly philosophical picture:

But what does it mean?

What does being Turing complete mean?

Is there a way to define the capabilities of Turing Machine without just saying “being able to simulate another Turing Machine”?

Informally speaking, being Turing complete means that your mechanism can run any algorithm you could think of, no matter how complex, deep, recursive, complicated, long (in terms of code) it is, and no matter how much storage or time would be needed to evaluate it. It goes without saying that it only succeeds if the problem is computable, but if it is computable, it will succeed (halt).

(N.B.: to find out why this is “informal”, check out the Church-Turing thesis which goes along those lines, with more elaborate wording; being a thesis, it could or could not be correct, though. Thanks to @DavidRicherby for pointing this little omission out in a comment.)

“Algorithm” means what we commonly understand as computer algorithm today; i.e., a series of discrete steps manipulating storage, with some control logic mixed in. It is not, however, like an Oracle machine, i.e., it cannot “guess”.

Example for a practical non-t.c. language

If you have programmed yourself, you probably know regular expressions, used to match strings to some pattern.

This is one example of a construct that is not Turing Complete. You can easily find exercises where it is simply impossible to create a regular expression that matches certain phrases.

For example (and this has surely vexed many programmer in actual real applications), it is theoretically and practically impossible to create a regular expression that matches a programming language or a XML document: it is impossible for a regexp to find the block structure (do ... end or { ... } in languages; opening and closing tags in XML documents) if they are allowed to be arbitrarily deep. If there is a limit there, for example you can only have 3 levels of “recursion”, then you could find a regular expression; but if it is not limited, then it’s a no go.

As it is obviously possible to create a program in a Turing-complete language (like C) to parse source code (any compiler does it), regular expressions will never be able to simulate said program, hence they are by definition not Turing-complete

Motivation

The idea of the turing machine in itself is nothing practical; i.e., Turing certainly did not invent it to create a real computer or something like that, as opposed to Charles Babbage or von Neumann, for example. The point of having the concept of the Turing Machine is that is exceedingly simple. It consists of almost nothing. It reduces possible (and actual) computers to the barest imaginable minimum.

The point of this simplification, in turn, is that this makes it easy(ish) to ponder about theoretical questions (like halting problems, complexity classes and whatever theoretical computer science bothers itself with). One feature in particular is that it is usually very easy to verify whether a given language or computer can simulate a Turing Machine by simply programming said Turing Machine (which is so easy!) in that language.

To infinity

Note that you never need infinite time or storage; but both time and storage are unbounded. They will have a maximal value for every single computable run, but there is no limit on how large that value can become. The fact that a real computer will eventually run out of RAM is glossed over here; this is of course a limit for any physical computer, but it also is obvious and of no interest to the theoretical “computing power” of the machine. Also, we are not interested about how long it actually takes, at all. So our little machine can use arbitrary amounts of time and space, which makes it absolutely impractical.

… and beyond

One astounding last point, then, is that such a simple, simple thing can do everything any conceivable real computer could ever, in the whole universe, accomplish (just very much slower) – at least as far as we know today.

Attribution
Source : Link , Question Author : sashoalm , Answer Author : Community

Leave a Comment