current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.6 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 262 down vote favorite
91

What does the expression "Turing Complete" mean?

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

share|improve this question
75  
Alan Turing is Skeet Complete. – tsilb Sep 9 '09 at 4:00
1  
Some very nice links at this SO question. – Lazer May 27 '10 at 15:56
    
@tsilb Jon Skeet is Turning Complete. How does he answer so many questions? He uses Skeet bots that (from accepted answer) "will find an answer". – Cole Johnson Aug 20 '13 at 0:34

11 Answers 11

up vote 157 down vote accepted

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.

share|improve this answer
14  
For further reading, see The Annotated Turing. Very approachable. amazon.com/Annotated-Turing-Through-Historic-Computability/d‌​p/… – i_am_jorf May 18 '09 at 17:19
9  
"often not in practice" is incorrect. No system is ever Turing-complete in practice, because no realizable system has an infinite tape. What we really mean is that some systems have the ability to approximate Turing-completeness up to the limits of their available memory. – Shelby Moore III Aug 8 '14 at 22:40
4  
But Vi is the only computational engine ever needed in the world... ;-) – Joe Edgar Aug 15 '14 at 5:07
2  
Is Emacs a Turning Machine too? XD – alem0lars Feb 16 '15 at 18:57
up vote 78 down vote

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'".

share|improve this answer
2  
In this context, what is a "computing device"? – dopatraman Nov 13 '14 at 16:43
up vote 27 down vote

Its often used to define "real" programming languages, where you can express any computation. Examining some languages that can't express all computations can help:

  • SQL
  • regular expressions
  • the language you enter into your four-function calculator
  • XML
  • Any programming language when restricted to 1KB of memory (or any finite amount of memory).

wikipedia on non-turing-complete languages

share|improve this answer
8  
SQL is most definitely turing-complete. It has scripting capabilities that allow for any computation. – nzifnab May 1 '11 at 0:41
45  
No, you are confusing SQL with extensions such as T-SQL / PL-SQL. ANSI SQL is not turing-complete. But TSQL / PLSQL - is. – Agnius Vasiliauskas Jul 3 '11 at 17:58
11  
Apparently SQL is turing-complete: stackoverflow.com/questions/900055/… – Newtang Jul 29 '12 at 23:59
2  
According to turing completeness - system is Turing complete if it can be used to simulate any single-taped Turing machine. But in example above as I understood devs constructed particular cyclic tag system and not universal cyclic tag system. Hence - article doesn't proves SQL turing completeness. (Or I misunderstood something) – Agnius Vasiliauskas Oct 2 '12 at 13:06
    
There is no realizable implementation of a Turing-complete language, because there are no infinite tapes. What we really mean is that some languages have the ability to approximate Turing-completeness up to the limits of the available memory of the host machine. – Shelby Moore III Aug 8 '14 at 22:34
up vote 17 down vote

Here is the simplest explanation

Alan Turing created a machine that can take a program and run that program and show some result. But then he had to create different machines for different programs. So he created "Universal Turing Machine" that can take ANY program and run it.

Programming languages are similar to those machines (although virtual). They take programs and run them. Now, a programing language is called "Turing complete", if that it can run any program(irrespective of the language) that a Turing machine can run given enough time and memory.

For example: Let's say there is a program that takes 10 numbers and adds them. Turing machine can easily run this program. But now imagine for some reason your programming language can't do the same addition then it's Turing machine incomplete. On the other hand, if it can run any program like the universal turing machine can run, then it's Turing complete.

Most modern programming languages like Java, JavaScript, Perl etc are all turing complete because they all implement all the features required to run programs like addition, multiplication, if-else condition, return statements, ways to store/retrieve/erase data and so on.

Update: You can learn more on my blog post: "JavaScript Is Turing Complete" — Explained

share|improve this answer
5  
+1 I've read dozens of SO question and answers and wikipedia articles. Your answer is the first one that explains this simply enough a child can understand. – spuder Oct 2 '16 at 15:24
3  
Best answer because of its simplicity, thanks! – Leo Dec 16 '16 at 18:31
up vote 12 down vote

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.

share|improve this answer
    
Finite state automata are allowed to have unbounded recursion. Case in point: a*. – user824425 Jun 4 '14 at 16:10
1  
@Rhymoid FSMs have limited memory—the finite # of states)—but unbounded recursion without tail optimization must have unlimited memory. I didn't restrict my definition to the subset of unbounded recursion only with tail optimization. Kindly remove your downvote. – Shelby Moore III Jul 23 '14 at 11:13
    
you kept the definition of unbounded recursion foggy. Do you mean 'recursion' in the 'primitive recursion' sense, and 'unbounded' by making it 'partial' (or 'general', or 'mu-')? Then you may be right. But your current formulation is way too close to the statements criticized in David Harel's "On Folk Theorems". It's important to be rigorous in mathematics, and by leaving precise definitions out, you're ignoring that. By the way: FSMs can be generalized to model interaction; what sets them apart from TMs is that the latter's environment is also modeled (as the tape). – user824425 Jul 23 '14 at 11:26
    
@Rhymoid enumeration is the antithesis of precision, e.g. enumerate the maximum precision of the fractions of an inch. Unbounded recursion means every possible form of recursion, which is impossible without an infinite tape. Fully generalized recursion (not just general within the model) is always Turing-complete. I am stating equivalence between generalized recursion and the ability to perform any possible computation. That is an important equivalence to note. – Shelby Moore III Aug 8 '14 at 22:22
    
"Unbounded recursion means every possible form of recursion" That's your reading. To most SO users, 'unbounded recursion' means while (p) { /* ... */ }. "I am stating equivalence between generalized recursion and the ability to perform any possible computation." Church's thesis is a very different matter and should really be discussed separately. – user824425 Aug 8 '14 at 23:20
up vote 8 down vote

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 (see Church-Turing Thesis).

share|improve this answer
2  
Note that all this disregards wall time. It just says "it can be done". – Thorbjørn Ravn Andersen Sep 27 '10 at 15:53
    
@ThorbjørnRavnAndersen actually, it disregards physical computability altogether. Not only could it take longer than the age of the universe, but it might also use more memory than can be constructed with all the fermions and bosons in the universe. – Waylon Flinn May 9 '16 at 17:25
up vote 6 down vote

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.

share|improve this answer
up vote 2 down vote

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.

share|improve this answer
up vote 0 down vote

As Waylon Flinn said:

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, i.e. 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.

share|improve this answer
    
I think you're assuming that the Church-Turing thesis is true to arrive at this conclusion. It has yet to be proven. The property you're describing is called 'Turing Equivalent'. – Waylon Flinn Dec 8 '09 at 13:41
    
@WaylonFlinn No, he's right. "Completeness" means both that it is at least as strong as a thing, but also no stronger. Compare with "NP-Complete". – Devin Jeanpierre Jan 23 '12 at 23:19
2  
@DevinJeanpierre I don't want to start a flame war here but I'm almost certain the computational class you're describing is called "Turing Equivalent". Turing Complete does bear a similar relation to NP-Complete though. NP-Complete is equal to NP if and only if P=NP. In the same way Turing Complete is equal to Turing Equivalent if and only if the Church-Turing thesis is correct. – Waylon Flinn Jan 27 '12 at 15:24
    
@Waylon Source? Nothing I read agrees with that (e.g. en.wikipedia.org/wiki/Turing_completeness ) – Devin Jeanpierre Jan 29 '12 at 16:09
3  
@DevinJeanpierre It says it right there in the wikipedia article you link to. Quoting the Formal definitions section: "A computational system that can compute every Turing-computable function is called Turing complete", "A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable" – Waylon Flinn Jan 31 '12 at 14:46
up vote 0 down vote

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

share|improve this answer
up vote -2 down vote

Can a relational database input latitudes and longitudes of places and roads, and compute the shortest path between them - no. This is one problem that shows SQL is not Turing complete.

But C++ can do it, and can do any problem. Thus it is.

share|improve this answer
9  
Being able to compute the shortest path between points is not the definition of Turing complete. There is so much more to it than just that one example. – Eva Feb 20 '13 at 23:48
    
I'll just put this here... hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.as‌​px – Matthew Whited Oct 23 '15 at 10:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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