What is Turing Complete?

Question

What does the expression Turing Complete means? Can you give a simple explanation, without going into too much theoretical details?

Answer 1

From wikipedia:

Turing completeness, named after Alan Turing, is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine — an observation that has become known as the Church-Turing thesis. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other programmable computer is capable of. However, this has nothing to do with the effort required to write a program for the machine, the time it may take for the machine to perform the calculation, or any abilities the machine may possess that are unrelated to computation.

While truly Turing-complete machines are very likely physically impossible, as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage. All modern computers are Turing-complete in this sense.

I don't know how you can be more non-technical than that except by saying "turing complete means 'able to answer computable problem given enough time and space'".

Answer 2

Here's the briefest explanation:

A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).

So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.

Sometime's it's a joke... a guy wrote a Turing Machine simulator in vi, so it's possible to say that vi is the only computational engine ever needed in the world.

Answer 3

I think the importance of the concept "Turing Complete" is in the the ability to identify a computing machine (not necessarily a mechanical/electrical "computer") that can have it's processes be deconstructed into "simple" instructions, composed of simpler and simpler instructions, that a Universal machine could interpret and then execute.

I highly recommend The Annotated Turing

@Mark i think what you are explaining is a mix between the description of the Universal Turing Machine and Turing Complete.

Something that is Turing Complete, in a practical sense, would be a machine/process/computation able to be written and represented as a program, to be executed by a Universal Machine (a desktop computer). Though it doesn't take consideration for time or storage, as mentioned by others.

Answer 4

Turing Complete means that it is at least as powerful as a Turing Machine. This means anything that can be computed by a Turing Machine can be computed by a Turing Complete system.

No one has yet found a system more powerful than a Turing Machine. So, for the time being, saying a system is Turing Complete is the same as saying the system is as powerful as any known computing system.

Answer 5

Waylon Flinn said above: """ Turing Complete means that it is at least as powerful as a Turing Machine. """ I believe this is incorrect, a system is Turing complete if it's exactly as powerful as the Turing Machine, ie every computation done by the machine can be done by the system, but also every computation done by the system can be done by the Turing machine. Cheers, Chris

Answer 6

Its often used to define "real" programming languages, where you can actually do most of what you want to. A better example is some languages that are not turing-complete, like SQL, XML, and JSON.

wikipedia on non-turing-complete languages