32
$\begingroup$

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"?

$\endgroup$
  • 31
    $\begingroup$ Lookup the definition of "turing machine". There's no circular definition, since a turing machine is not defined as "being able to simulate another turing machine" - it's a fully designed theoretical computer (basically, an infinite tape state machine). You're just mixing up "turing-complete" and "turing machine". As far as I know, we still don't know of any algorithms that can't run on a turing machine, but that might be just my own ignorance. $\endgroup$ – Luaan Mar 13 '17 at 14:10
  • 2
    $\begingroup$ @Luaan The Church-Turing Thesis would agree with you. $\endgroup$ – Brian McCutchon Mar 14 '17 at 3:31
  • $\begingroup$ "Is there a way to define the capabilities of Turing Machine". Sure. Theory goes into how much space and time is required to solve algorithms with Turing machines (L, NL, P, NP, PSPACE, etc..), and there are also problems that cannot be solved (which can usually be solved by reductions to other unsolvable problems). One example of a problem that cannot be solved by Turing machines is the halting problem. $\endgroup$ – Millie Smith Mar 14 '17 at 4:10
  • $\begingroup$ When it comes to CS (or any other) theory, it is always better to read a book on topic than to google it and read few blog posts on topic that are, in many cases, written by people who don't fully understand topic themselves. One good book will save you time, give you wider picture and better understanding. $\endgroup$ – Bozidar Sikanjic Mar 14 '17 at 13:00
  • $\begingroup$ The Ackermann function is a prominent example of something that a Turing machine can calculate but a more limited model of computation (primitive recursion) can't. $\endgroup$ – zwol Mar 14 '17 at 20:49
12
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Informally speaking, being Turing complete means that your mechanism can run any algorithm you could think of" Well, that relies on accepting the Church-Turing thesis, which says that Turing machines can implement any algorithm you can think of. Or, alternatively, you could take Turing machines as the definition of algorithm, in which case the informal statement is just an informal version of "can simulate any Turing machine" (which isn't a bad thing; just an observation). $\endgroup$ – David Richerby Mar 14 '17 at 22:29
  • $\begingroup$ My impression was that the OP asks about an intuitive understanding what it means to be turing complete. Hence, this kind of flippant, non-theoretical-computer-science answer. Thanks for pointing this out, I'll integrate it into the answer. @DavidRicherby $\endgroup$ – AnoE Mar 14 '17 at 23:14
  • $\begingroup$ Thanks! That's the kind of answer I was looking for. I was thinking about the halting problem, and how languages with simple bounded for-loops are predictable (they always halt) - and thus non-Turing complete. I was thinking maybe being Turing-complete means being potentially unpredictable in some way (is chaotic the right term for those functions?) $\endgroup$ – sashoalm Mar 15 '17 at 15:25
  • $\begingroup$ @sashoalm, glad you like the answer. No, unpredictability does not really factor into the issue. Bounded for-loops (as non-tc) is a nice example, too. In fact, another good example for a simple (and more real-world) tc language would be one which just has variables and (unbounded) while - that is already enough to be tc. The (un)boundedness of the control structure is one of the key elements. $\endgroup$ – AnoE Mar 15 '17 at 16:49
38
$\begingroup$

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.)

$\endgroup$
  • 19
    $\begingroup$ I think OP mixes up Turing machine and Turing complete. What he's actually looking for is the definition of a Turing machine; your last sentence is the answer. en.wikipedia.org/wiki/Turing_machine would help. $\endgroup$ – JollyJoker Mar 13 '17 at 14:38
  • $\begingroup$ So what can a Turing machine do? As in, if I wanted to prove that something can emulate a Turing machine, what minimal set of behaviours must I be able to demonstrate that my machine can do too? $\endgroup$ – Akshat Mahajan Mar 14 '17 at 23:06
  • 2
    $\begingroup$ Never mind - I worked out that it is sufficient to demonstrate that a language can mimic the way a Turing machine operates in order to prove that it is Turing-complete. $\endgroup$ – Akshat Mahajan Mar 14 '17 at 23:14
17
$\begingroup$

Turing's model of computation is just one of many equivalent models of computation. It has the same power as Gödel's recursive functions and Church's lambda calculus, which were proposed around the same time, as well as other models such as the pointer machine. You can therefore state that

A computer is Turing-complete if it can solve any problem that Excel can.

This works since Excel is also Turing-complete. I recommend taking a look at Wikipedia's page on the Church-Turing thesis, and at a survey paper of Blass and Gurevich, Algorithms: A Quest for Absolute Definitions.


Regarding your question, what can a Turing machine do that a non-Turing machine cannot, in general the answer unfortunately depends on the non-Turing machine.

It is possible, however, to define non-trivial notions of Turing-complete problems, for example:

A language $L$ is Turing-complete if for every computable language $A$ there exists an "efficiently computable" function $f$ such that $a \in A$ iff $f(a) \in L$.

Under this definition, suitable encodings of the halting problem are Turing-complete, and so for a reasonable class of machines (depending on the definition of "efficiently computable"), the machine is Turing-complete iff it can realize some (equivalently, all) Turing-complete language.

There are many other Turing-complete problems captured by this formalism, depending on the definition of "efficiently computable", such as the Turing correspondence problem, and problems concerning Wang tiles and the Game of Life. Any of these problems can function as a benchmark instead of the halting problem.

$\endgroup$
  • $\begingroup$ "the answer unfortunately depends on the non-Turing machine" - I edited my question because it wasn't clear. You can choose any non-Turing machine, so long as it can perform the task while remaining non-Turing-complete. $\endgroup$ – sashoalm Mar 13 '17 at 13:29
  • 5
    $\begingroup$ Excel is also Turing-complete. -- only if you can give Excel infinite memory. Excel is limited to 1,048,576 rows and 16,384 columns, which is a good deal short of infinite. $\endgroup$ – MattClarke Mar 14 '17 at 3:14
  • 5
    $\begingroup$ @MattClarke: True, but by the same token no system ever built is Turing-complete. $\endgroup$ – Emil Mar 14 '17 at 7:37
  • 3
    $\begingroup$ @Emil: exactly, and it's important that students of CS distinguish between the capabilities of computation models and the capabilities of actual machines. Those of us who've repeatedly hit the physical limits of our actual machines find this distinction easy to make, of course. So we sort of know how we'd define an unrestricted version of Excel's computing model, and that it would be Turing-complete. Even though actually writing out that definition is kind of fiddly. $\endgroup$ – Steve Jessop Mar 14 '17 at 12:59
  • 4
    $\begingroup$ @SteveJessop Physical limits of machines? How could anyone hit such a thing? 640k is enough for anyone! $\endgroup$ – David Richerby Mar 14 '17 at 19:31
4
$\begingroup$

First of all I wish to point out that the definition of Turing-completeness isn't tautological at all. Not only proving a computational model Turing-complete is an interesting result in itself, but it also allows you to immediately extend all the results from computability theory to this other computational model; for example: 2-counter machines are Turing-complete, Turing machines cannot solve the halting problem, therefore neither 2-counter machines can.

A simple characterization of the functions computable by a Turing machine is given by the $\mu$-recursive functions, the minimal set of functions closed under composition, primitive recursion and minimization operator that contains the constantly zero function, the identity and the successor function.

Such class incorporates those functions that are "intuitively computable", that is, which computation could be carried out by a human following a precise algorithm with pencil and paper.

Obviously "intuitively computable" isn't really a formal definition, the identification of "intuitively computable" with "Turing computable" is known as the Church-Turing thesis. Since many formal attempts to characterize computability ultimately converge to a computational model that is Turing-complete, although there will never be a formal proof of such an assertion in a mathematical sense, there are strong reasons to believe it.

$\endgroup$
0
$\begingroup$

A Turing machine has the can compute the same set of functions as a universal quantum computer, which can simulate any physical system:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

As such, a Turing machine is capable of doing any information processing allowed by the laws of physics, although it won't always do such processing as efficiently as possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.