What is Turing Complete?

Question

What does the expression "Turing Complete" mean?

Can you give a simple explanation, without going into too many theoretical details?

Answer 1

In practical language terms familiar to most programmers, the usual way to detect Turing completeness is if the language allows or allows the simulation of nested unbounded while statements (as opposed to Pascal-style for statements, with fixed upper bounds).

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

In the simplest terms, a Turing-complete system can solve any possible computational problem.

One of the key requirements is the scratchpad size be unbounded and that is possible to rewind to access prior writes to the scratchpad.

Thus in practice no system is Turing-complete.

Rather some systems approximate Turing-completeness by modeling unbounded memory and performing any possible computation that can fit within the system's memory.

Answer 4

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 its 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 5

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 6

Fundamentally, Turing-completeness is one concise requirement, unbounded recursion.

Not even bounded by memory.

I thought of this independently, but here is some discussion of the assertion. My definition of LSP provides more context.

The other answers here don't directly define the fundamental essence of Turing-completeness.