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?

Margarita

Answer 1

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.

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

Barrel

For further reading, see The Annotated Turing. Very approachable. amazon.com/Annotated-Turing-Through-Historic-Computability/dp/… – Indo

"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. – Eaten

But Vi is the only computational engine ever needed in the world... ;-) – Ballarat

Is Emacs a Turning Machine too? XD – Forestall

Someone recently showed that PowerPoint is Turing Complete too. – Flatten

Is “any computation problem” solvable as long as your program can correctly +, –, ×, and ÷? Or does it require more? Do we know what the ability to solve “any computation problem” requires, or is that a bit of debatable mystery? – Inutility

@JacobFord and an infinite amount of randomly accessible scratch space, and an ability to make decisions and loops – Mraz

Whenever someone claims something is Turing complete, I think it's worth pointing out that a Turing Machine has been made in the Game of Life. (1 cycle takes 11040 generations) – Deliver

What kinds of things are decidable by a Turing Machine and undecidable by a machine that is otherwise Turing Equivalent except for having finite rather than unlimited memory? – Remedial

I see what you are saying now: For every computation C that is decidable on a Turing Machine M that is decidable on another machine N this other machine N is Turing complete for this computation C. Thus the "C" programming language and corresponding real world machines having finite memory are Turing Complete for every decidable computation that is also decidable by a Turing Machine. – Remedial

By this analogy - how can we explain power point is Turing complete ? – Enrollee

@Forestall Yes. – Outpatient

I think this response could be improved by listing the properties that make it to be Turing complete, rather than just stating that the thing does what a Turing machine would do. – Noctule

Answer 2

Here is the simplest explanation

Alan Turing created a machine that can take a program, 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 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. A Turing machine can easily run this program. But now imagine that for some reason your programming language can't perform the same addition. This would make it "Turing incomplete" (so to speak). On the other hand, if it can run any program that the universal Turing machine can run, then it's Turing complete.

Most modern programming languages (e.g. Java, JavaScript, Perl, etc.) are all Turing complete because they each 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

Tore

The idea that there would even be a term for this kind of machine makes a lot more sense when I remember Turing and other early computer scientists would build a specific machine each time they wanted to solve a specific problem. We’re used to one machine that can be forever reprogrammed. Thank you for the context, Raja. – Inutility

How JavaScript can be Turing Complete? It lacks file system , proper multithreading API . It has tons of limitations, mainly due to its browser security sandbox nature. It's hardly can be called ' a programming language ' .See how many variants of scripting abstraction exist (react, typescript ..you name it) ,all that to compensate what JS doesn't have. (asm.js should be mentioned here) . Java ,Python or C++ are true 'Turing Complete ' examples. But js? I don't think so. – Sharell

@MichaelIV The touring machine did not have a file system/threads either. JS is absolutely touring complete. – Territorial

@MichaelIV To add to Bax's response, one could consider a modern computer to consist of several Turing machines that work together to allow for all of those nice things that you mention. E.g. the CPU produces "tape" for the GPU to read so that it can write "tape" for the monitor so that the monitor can write "tape" to the user. Likewise, the CPU could produce "tape" for the hard drives, NICs, sound cards, etc. – Shogunate

the blog post link is broken – Scutate

JS is absolutely Turing complete - but Turing completeness is a lower bar than you might be imagining. It doesn't mean it's optimal for any computation. For example: A language doesn't need to be able to multiply numbers to be turing complete if it can add numbers, loop and perform conditional statements. It's turing complete because you could write a function to multiply numbers with that other functionality. – Accomplished

@KyleAlm also adding to this: adding numbers is overrated as well. increment, decrement and some conditionals are enough for addition. With addition we can make multiplication. (I know you are aware, but saying it for other people who might not have thought about it). Reminder that BF is also turing complete even with just add, dec, next variable, last variable and loop if zero. – Inapposite

Answer 3

Informal Definition

A Turing complete language is one that can perform any computation. The Church-Turing Thesis states that any performable computation can be done by a Turing machine. A Turing machine is a machine with infinite random access memory and a finite 'program' that dictates when it should read, write, and move across that memory, when it should terminate with a certain result, and what it should do next. The input to a Turing machine is put in its memory before it starts.

Things that can make a language NOT Turing complete

A Turing machine can make decisions based on what it sees in memory - The 'language' that only supports +, -, *, and / on integers is not Turing complete because it can't make a choice based on its input, but a Turing machine can.

A Turing machine can run forever - If we took Java, Javascript, or Python and removed the ability to do any sort of loop, GOTO, or function call, it wouldn't be Turing complete because it can't perform an arbitrary computation that never finishes. Coq is a theorem prover that can't express programs that don't terminate, so it's not Turing complete.

A Turing machine can use infinite memory - A language that was exactly like Java but would terminate once it used more than 4 Gigabytes of memory wouldn't be Turing complete, because a Turing machine can use infinite memory. This is why we can't actually build a Turing machine, but Java is still a Turing complete language because the Java language has no restriction preventing it from using infinite memory. This is one reason regular expressions aren't Turing complete.

A Turing machine has random access memory - A language that only lets you work with memory through push and pop operations to a stack wouldn't be Turing complete. If I have a 'language' that reads a string once and can only use memory by pushing and popping from a stack, it can tell me whether every ( in the string has its own ) later on by pushing when it sees ( and popping when it sees ). However, it can't tell me if every ( has its own ) later on and every [ has its own ] later on (note that ([)] meets this criteria but ([]] does not). A Turing machine can use its random access memory to track ()'s and []'s separately, but this language with only a stack cannot.

A Turing machine can simulate any other Turing machine - A Turing machine, when given an appropriate 'program', can take another Turing machine's 'program' and simulate it on arbitrary input. If you had a language that was forbidden from implementing a Python interpreter, it wouldn't be Turing complete.

Examples of Turing complete languages

If your language has infinite random access memory, conditional execution, and some form of repeated execution, it's probably Turing complete. There are more exotic systems that can still achieve everything a Turing machine can, which makes them Turing complete too:

• Untyped lambda calculus
• Conway's game of life
• C++ Templates
• Prolog

Nightly

SQL is most definitely turing-complete. It has scripting capabilities that allow for any computation. – Manageable

No, you are confusing SQL with extensions such as T-SQL / PL-SQL. ANSI SQL is not turing-complete. But TSQL / PLSQL - is. – Backtrack

Apparently SQL is turing-complete: stackoverflow.com/questions/900055/… – Lezlielg

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) – Backtrack

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. – Eaten

Conway's Game of Life is Turing complete too. en.wikipedia.org/wiki/Conway's_Game_of_Life – Smetana

@Ejaz, No, it is a type of data representation. see stackoverflow.com/questions/15488658/… for more information – Protamine

What do you mean by saying “Regular expressions aren’t Turing complete”? RE’s perform computations to arrive at a certain result - just like any program would. Could you please explain? – Connection

Thanks, in my opinion this was by far the easiest-to-understand answer – Trunk

@Connection Regular expressions aren’t Turing complete because they can't do certain computations (like checking if a number is prime) that a Turing Machine can. – Nightly

Answer 4

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

Ahouh

In this context, what is a "computing device"? – Cadre

As with most Wikipedia articles, although this quote is technically correct, it provides no value to a person who has no knowledge on the subject and is trying to understand it. Being able to explain things properly is a science of its own :) – Marginalia

Circular definition. "Turing-Complete" is something that can run a "universal Turing machine". Begs the question: What's a "Turing"... the answer for which is again, not helpful. – Dromedary

Answer 5

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

Arhat

Note that all this disregards wall time. It just says "it can be done". – Copyhold

@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. – Arhat

There is, quitte possibly, no limit to the amount of bosons and fermions in the universe. We don't know, and will probably never know, it's size. Every time you read about the number of X in 'the universe', people are actually talking about the observable universe. Though interesting, it is not an actual physical limit. – Reduce

Usually by powerfull one understand "compute fast" (a concept to put beside complexity (complexity theory)), a TM is complete if it finishes (computable (computability theory)). This answer is misleading if not wrong due to the approximate or wrong wording. – Gauldin

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.

Eaten

Finite state automata are allowed to have unbounded recursion. Case in point: a*. – Retroaction

@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. – Eaten

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

@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. – Eaten

"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. – Retroaction

@Rhymoid unhalting loops sans side-effects, compute precisely nothing. (With side-effects computation is fully generalized within the model.) Obviously I couldn't mean that given Turing-completeness is about the generality of computation. Saying more with less words is a high IQ trait (note I didn't claim it is best when communicating to all audiences). Relating Church's equivalence to more succinct understanding of Turing-completeness is relevant here. Thanks for the discussion and pointers. Hopefully it clarifies. – Eaten

In your answer it stated: "Fundamentally, Turing-completeness is one concise requirement, unbounded recursion. Not even bounded by memory.", I assumed this to mean "not even bounded by the limited memory". Though in comments you say: "Unbounded recursion means every possible form of recursion, which is impossible without an infinite tape." My understanding is that, for Turing Machine, tape = memory, it follows herefrom that nothing is Turing-Complete, since nothing has infinite memory. What am I missing or misunderstanding here? Could you please, kindly, elaborate? – Cheri

I think, I have found answer to my own question, in this article, which states: "...unbounded recursion — i.e. the ability to invoke small programs (a.k.a. functions) which can invoke themselves ad infinitum.", as I grasped it, this means, that unbounded recursion (as implied by it's name =) is ability to recurse unbounded, but finite (meaning that actual amount of steps is finite, but you can always do n+1 steps) amount of times. – Cheri

Answer 7

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.

Eaten

Answer 8

Super-brief summary from what Professor Brasilford explains in this video.

Turing Complete ≅ do anything that a Turing Machine can do.

1. It has conditional branching (i.e. "if statement"). Also, implies "go to" and thus permitting loop.

2. It gets arbitrary amount of memory (e.g. long enough tape) that the program needs.

Vitovitoria

Answer 9

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.

Azygous

Answer 10

A Turing Machine requires that any program can perform condition testing. That is fundamental.

Consider a player piano roll. The player piano can play a highly complicated piece of music, but there is never any conditional logic in the music. It is not Turing Complete.

Conditional logic is both the power and the danger of a machine that is Turing Complete.

The piano roll is guaranteed to halt every time. There is no such guarantee for a TM. This is called the “halting problem.”

Boutin

Answer 11

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

Kreit

A single unbounded while loop is enough to simulate a Turing machine. – Entrain

Answer 12

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.

Acarus

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'. – Arhat

@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". – Phycomycete

@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. – Arhat

@Waylon Source? Nothing I read agrees with that (e.g. en.wikipedia.org/wiki/Turing_completeness ) – Phycomycete

@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" – Arhat

@WaylonFlinn You wrote that "Turing Complete is equal to Turing Equivalent if and only if the Church-Turing thesis is correct." Isn't Turing Equivalence a broader concept? Two systems can be turing equivalent with one another, although they may only be capable of a subset of computations of a Turing machine. Hence, Turing Completeness is Turing Equivalence with respect to a Universal Turing Machine. – Feodore

Every computation done by a Turing complete machine will obviously be possible on a Turing Machine. What is of interest insofar as describing a Turing Complete machine would be that it is able to do all the computations possible on a Turing Machine – Connection

Answer 13

We call a language Turing-complete if and only if (1) it is decidable by a Turing machine but (2) not by anything less capable than a Turing machine. For instance, the language of palindromes over the alphabet {a, b} is decidable by Turing machines, but also by pushdown automata; so, this language is not Turing-complete. Truly Turing-complete languages - ones that require the full computing power of Turing machines - are pretty rare. Perhaps the language of strings x.y.z where x is a number, y is a Turing-machine and z is an initial tape configuration, and y halts on z in fewer than x! steps - perhaps that qualifies (though it would need to be shown!)

A common imprecise usage confuses Turing-completeness with Turing-equivalence. Turing-equivalence refers to the property of a computational system which can simulate, and which can be simulated by, Turing machines. We might say Java is a Turing-equivalent programming language, for instance, because you can write a Turing-machine simulator in Java, and because you could define a Turing machine that simulates execution of Java programs. According to the Church-Turing thesis, Turing machines can perform any effective computation, so Turing-equivalence means a system is as capable as possible (if the Church-Turing thesis is true!)

Turing equivalence is a much more mainstream concern that true Turing completeness; this and the fact that "complete" is shorter than "equivalent" may explain why "Turing-complete" is so often misused to mean Turing-equivalent, but I digress.

Neona

Answer 14

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.

Northward

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. – Endoderm

I'll just put this here... hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.aspx – Sarena