What is Turing Complete?

528

What does the expression "Turing Complete" mean?

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

This question is tagged with theory turing-machines turing-complete

~ Asked on 2008-08-10 18:41:02

15 Answers


363

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.

~ Answered on 2008-08-10 20:10:48


219

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

~ Answered on 2016-05-16 05:17:26


85

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

~ Answered on 2009-10-22 23:45:42


84

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

~ Answered on 2008-08-10 18:59:06


17

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.

~ Answered on 2011-11-27 04:03:15


13

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

~ Answered on 2009-05-18 17:09:11


9

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.

~ Answered on 2014-08-08 22:50:53


3

What i understand in simple words:

Turing Complete : A programming language / program that can do computation, is Turing complete.

For example :

  1. Can you add two numbers using Just HTML. (Ans is 'No', you have to use javascript to perform addition.), Hence HTML is not Turing Complete.

  2. Languages like Java , C++, Python, Javascript, Solidity for Ethereum etc are Turing Complete because you can do computation like adding two numbers using this languages.

Hope this helps.

~ Answered on 2018-12-28 15:39:42


2

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.

~ Answered on 2008-08-20 07:23:29


0

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 has arbitrary amount of memory (e.g. long enough tape) that the program needs.

~ Answered on 2021-02-18 13:08:15


-1

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

~ Answered on 2020-03-18 20:18:20


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

~ Answered on 2016-10-26 20:12:17


-3

Its complete if it can test and branch (has an 'if')

~ Answered on 2020-01-15 17:10:05


-3

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.

~ Answered on 2009-10-05 23:18:19


-9

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.

~ Answered on 2012-12-15 18:33:53


Most Viewed Questions: