Turing completeness
Encyclopedia
In computability theory, a system of data-manipulation rules (such as an instruction set
, a programming language
, or a cellular automaton
) is said to be Turing complete or computationally universal if and only if
it can be used to simulate any single-taped Turing machine
and thus in principle any computer
. A classic example is the lambda calculus
. The concept is named after Alan Turing
.
In practice, Turing completeness means that the rules followed in sequence on arbitrary data can produce the result of any calculation. In procedural languages this can be satisfied by having, at a minimum, conditional branching (e.g., an "if" and "goto" statement) and the ability to change arbitrary memory
locations (e.g., variables). To show that something is Turing complete, it is enough to show that it can be used to simulate the most primitive computer, since even the simplest computer can be used to simulate the most complicated one. All general purpose programming languages and modern machine instruction sets are Turing complete, notwithstanding finite-memory limitations.
A universal computer is defined as a device with a Turing complete instruction set, infinite memory, and an infinite lifespan. All real-world systems necessarily have finite memory, making the true universal computer a theoretical construct.
In computability theory, there is a closely related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine. The reason is that any real world computer can be simulated by a Turing machine, an observation codified as the Church–Turing thesis
.
A computer with access to an infinite tape of data is sometimes more powerful than a Turing machine, because the tape can in principle contain the solution to the halting problem
, or some other undecidable problem. An infinite tape of data is called a Turing oracle. Even a Turing oracle with random data is not computable (with probability 1), since there are only countably many computations but uncountably many oracles. So a computer with a random Turing oracle can compute things that a Turing machine cannot. A machine which is universal except for having access to some Turing oracle is called weakly universal.
or programming language
):
Turing completeness
Turing equivalence
(Computational) universality
, is significant in that every real-world design for a computing device can be simulated by a universal Turing machine
. The Church–Turing thesis
states that this is a law of nature—that a universal Turing machine can, in principle, perform any calculation that any other programmable computer
can. Obviously, this says nothing about the effort needed to write the program
, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation.
While truly Turing-complete machines need unlimited amounts of working memory, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage and addressing. All modern computers are Turing complete in this loose sense, they are linear bounded automaton complete
.
Charles Babbage
's analytical engine
(1830s) would have been the first Turing-complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform an "if/goto" and therefore are not true computers.
In the late 19th century, Leopold Kronecker
formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert
led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel
in 1930. Gödel's completeness theorem
of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church then Turing identified the computational core of the incompleteness theorem, and were able to produce undecidable problems. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
John von Neumann
was inspired by these results to design actual working universal computing machines. The first formal programming languages of the 1930s demonstrated that such a computer would be useful. The first actual implementation of a Turing-complete machine appeared in 1941: the program-controlled Z3 of Konrad Zuse
, but the first machine explicitly designed to be Turing complete and widely appreciated as being universal was the 1946 ENIAC
. This machine was able to solve a wide range of effective problems in the 1940s, many related to atomic bomb design.
All known laws of physics have consequences which are computable by a series of approximations on a digital computer. A hypothesis called digital physics
states that this is no accident, that it is because the universe
itself is computable on a universal Turing machine. This would imply that no computer more powerful than a universal Turing machine can be built physically (see philosophical implications in the Church–Turing thesis).
). It is impossible to determine whether the program will return "true" or whether it will return "false". For any characteristic of the program's eventual output, it is impossible to determine whether this characteristic will hold. This can cause problems in practice when analyzing real-world computer programs. One way to avoid this is to cause programs to stop executing after a fixed period of time, or to limit the power of flow control instructions. Such systems are not Turing complete by design.
Another theorem shows that there are problems solvable by Turing-complete languages that cannot be solved by any language with only finite looping abilities (i.e., any language that guarantees every program will eventually finish to a halt). Given a guaranteed halting language, the computable function which is produced by Cantor's diagonal argument
on all computable functions in that language is not computable in that language.
. They are intended to be as simple as possible, so that it would be easier to understand the limits of computation. Here are a few:
Most programming language
s, conventional and unconventional, are Turing-complete. This includes:
The specific language features used to achieve Turing completeness can be quite different; Fortran
systems would use loop constructs or possibly even goto
statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use recursion
. Turing completeness is an abstract statement of ability, rather than a prescription of specific language features used to implement that ability.
Turing completeness in SQL
is implemented through advanced standard features, illustrating one reason relatively powerful non-Turing-complete languages are rare: the more powerful the language is initially, the more complex are the tasks to which it is applied and the sooner its lack of completeness becomes perceived as a drawback, encouraging its extension until it is Turing complete.
The untyped lambda calculus
is Turing complete, but many typed lambda calculi, including System F
, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.
Rule 110 and Conway's Game of Life
, both cellular automata
, are Turing complete.
s, most commonly regular expression
s, which are generated by finite automata
. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata
and context-free grammar
s, which are commonly used to generate parse trees in an initial stage of program compiling
. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D
and OpenGL
extensions, or a series of mathematical formulae in a spreadsheet
with no cycles.
In some languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory
, whereas Epigram uses dependent type
s.
, JSON
, YAML
and S-expression
s are not Turing complete because they are only used to represent structured data, not describe computation. These are sometimes referred to as markup language
s, or more properly as "data description languages".
Non-Turing complete languages, especially data languages, are desirable in that they can be manipulated, which, however, also applies to some Turing-complete languages, most notably Lisp and many of its dialects like Scheme. This is codified in the web design principle known as the "Rule of Least Power", which recommends avoiding the use of Turing complete languages, and in fact using the least powerful language that satisfies a task, so that the result data can more easily be reused and transformed.
Instruction set
An instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...
, a programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
, or a cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
) is said to be Turing complete or computationally universal if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
it can be used to simulate any single-taped Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
and thus in principle any computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
. A classic example is the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
. The concept is named after Alan Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
.
In practice, Turing completeness means that the rules followed in sequence on arbitrary data can produce the result of any calculation. In procedural languages this can be satisfied by having, at a minimum, conditional branching (e.g., an "if" and "goto" statement) and the ability to change arbitrary memory
Computer memory
In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
locations (e.g., variables). To show that something is Turing complete, it is enough to show that it can be used to simulate the most primitive computer, since even the simplest computer can be used to simulate the most complicated one. All general purpose programming languages and modern machine instruction sets are Turing complete, notwithstanding finite-memory limitations.
A universal computer is defined as a device with a Turing complete instruction set, infinite memory, and an infinite lifespan. All real-world systems necessarily have finite memory, making the true universal computer a theoretical construct.
In computability theory, there is a closely related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine. The reason is that any real world computer can be simulated by a Turing machine, an observation codified as the Church–Turing thesis
Church–Turing thesis
In computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...
.
A computer with access to an infinite tape of data is sometimes more powerful than a Turing machine, because the tape can in principle contain the solution to the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, or some other undecidable problem. An infinite tape of data is called a Turing oracle. Even a Turing oracle with random data is not computable (with probability 1), since there are only countably many computations but uncountably many oracles. So a computer with a random Turing oracle can compute things that a Turing machine cannot. A machine which is universal except for having access to some Turing oracle is called weakly universal.
Formal definitions
In computability theory, several closely related terms are used to describe the computational power of a computational system (such as an abstract machineAbstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
or programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
):
Turing completeness
- A computational system that can compute every Turing-computable functionComputable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machineUniversal Turing machineIn computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
.
Turing equivalence
- A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing equivalent, which adds support to the Church–Turing thesisChurch–Turing thesisIn computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...
.)
(Computational) universality
- A system is called universal with respect to a class of systems if it can compute every function computable by systems in that class (or can simulate each of those systems). Typically, the term universality is tacitly used with respect to a Turing-complete class of systems. The term "weakly universal" is sometimes used to distinguish a system (e.g. a cellular automatonCellular automatonA cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
) whose universality is achieved only by modifying the standard definition of Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
so as to include input streams with infinitely many 1s.
Overview
Turing completeness, named after Alan TuringAlan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
, is significant in that every real-world design for a computing device can be simulated by a universal Turing machine
Universal Turing machine
In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
. The Church–Turing thesis
Church–Turing thesis
In computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...
states that this is a law of nature—that a universal Turing machine can, in principle, perform any calculation that any other programmable computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
can. Obviously, this says nothing about the effort needed to write the program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation.
While truly Turing-complete machines need unlimited amounts of working memory, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage and addressing. All modern computers are Turing complete in this loose sense, they are linear bounded automaton complete
Linear bounded automaton
In computer science, a linear bounded automaton is a restricted form of nondeterministic Turing machine.-Operation:Linear bounded automata satisfy the following three conditions:...
.
Charles Babbage
Charles Babbage
Charles Babbage, FRS was an English mathematician, philosopher, inventor and mechanical engineer who originated the concept of a programmable computer...
's analytical engine
Analytical engine
The Analytical Engine was a proposed mechanical general-purpose computer designed by English mathematician Charles Babbage. It was first described in 1837 as the successor to Babbage's difference engine, a design for a mechanical calculator...
(1830s) would have been the first Turing-complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform an "if/goto" and therefore are not true computers.
In the late 19th century, Leopold Kronecker
Leopold Kronecker
Leopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...
formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
in 1930. Gödel's completeness theorem
Gödel's completeness theorem
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. It was first proved by Kurt Gödel in 1929....
of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church then Turing identified the computational core of the incompleteness theorem, and were able to produce undecidable problems. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
was inspired by these results to design actual working universal computing machines. The first formal programming languages of the 1930s demonstrated that such a computer would be useful. The first actual implementation of a Turing-complete machine appeared in 1941: the program-controlled Z3 of Konrad Zuse
Konrad Zuse
Konrad Zuse was a German civil engineer and computer pioneer. His greatest achievement was the world's first functional program-controlled Turing-complete computer, the Z3, which became operational in May 1941....
, but the first machine explicitly designed to be Turing complete and widely appreciated as being universal was the 1946 ENIAC
ENIAC
ENIAC was the first general-purpose electronic computer. It was a Turing-complete digital computer capable of being reprogrammed to solve a full range of computing problems....
. This machine was able to solve a wide range of effective problems in the 1940s, many related to atomic bomb design.
All known laws of physics have consequences which are computable by a series of approximations on a digital computer. A hypothesis called digital physics
Digital physics
In physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable...
states that this is no accident, that it is because the universe
Universe
The Universe is commonly defined as the totality of everything that exists, including all matter and energy, the planets, stars, galaxies, and the contents of intergalactic space. Definitions and usage vary and similar terms include the cosmos, the world and nature...
itself is computable on a universal Turing machine. This would imply that no computer more powerful than a universal Turing machine can be built physically (see philosophical implications in the Church–Turing thesis).
Computability theory
The first result of computability theory is that it is impossible in general to predict what a Turing-complete program will do over an arbitrarily long time. For example, it is impossible to determine for every program-input pair whether the program, operating on the input, will eventually stop or will continue forever (see halting problemHalting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
). It is impossible to determine whether the program will return "true" or whether it will return "false". For any characteristic of the program's eventual output, it is impossible to determine whether this characteristic will hold. This can cause problems in practice when analyzing real-world computer programs. One way to avoid this is to cause programs to stop executing after a fixed period of time, or to limit the power of flow control instructions. Such systems are not Turing complete by design.
Another theorem shows that there are problems solvable by Turing-complete languages that cannot be solved by any language with only finite looping abilities (i.e., any language that guarantees every program will eventually finish to a halt). Given a guaranteed halting language, the computable function which is produced by Cantor's diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...
on all computable functions in that language is not computable in that language.
Examples
The computational systems (algebras, calculi) that are discussed as Turing complete systems are those intended for studying theoretical computer scienceTheoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
. They are intended to be as simple as possible, so that it would be easier to understand the limits of computation. Here are a few:
- Automata theoryAutomata theoryIn theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
- Universal Turing machineUniversal Turing machineIn computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
- Lambda calculusLambda calculusIn mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
- Formal grammarFormal grammarA formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
(language generators) - Formal languageFormal languageA formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
(language recognizers) - Rewrite system
- Post–Turing machines
Most programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s, conventional and unconventional, are Turing-complete. This includes:
- All general-purpose languages in wide use.
- Procedural programmingProcedural programmingProcedural programming can sometimes be used as a synonym for imperative programming , but can also refer to a programming paradigm, derived from structured programming, based upon the concept of the procedure call...
languages such as PascalPascal (programming language)Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
. - Object-orientedObject-oriented programming languageThis is a list of object-oriented programming programming languages.-Languages with object-oriented features:*ABAP*Ada 95*AmigaE*BETA*Blue*Boo*C++*C#*COBOL*Cobra*ColdFusion*Common Lisp*COOL*CorbaScript*Clarion*CLU*Curl*D*Dylan*E*Eiffel...
languages such as JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, SmalltalkSmalltalkSmalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
. - Multi-paradigmMulti-paradigm programming languageProgramming languages can be grouped by the number and types of paradigms supported.-Paradigm summaries:A concise reference for the programming paradigms listed in this article....
languages such as AdaAda (programming language)Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
, C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, Common LispCommon LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
, Object PascalObject PascalObject Pascal refers to a branch of object-oriented derivatives of Pascal, mostly known as the primary programming language of Embarcadero Delphi.-Early history at Apple:...
.
- Procedural programming
- Most languages using less common paradigms
- FunctionalFunctional programmingIn computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
languages such as Lisp and HaskellHaskell (programming language)Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
. - Logic programmingLogic programmingLogic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
languages such as PrologPrologProlog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
. - DeclarativeDeclarative programmingIn computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...
languages such as XSLTXSLTXSLT is a declarative, XML-based language used for the transformation of XML documents. The original document is not changed; rather, a new document is created based on the content of an existing one. The new document may be serialized by the processor in standard XML syntax or in another format,...
. - Esoteric programming languageEsoteric programming languageAn esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...
s, such as brainfuckBrainfuckThe brainfuck programming language is an esoteric programming language noted for its extreme minimalism. It is a Turing tarpit, designed to challenge and amuse programmers, and is not suitable for practical use...
.
- Functional
The specific language features used to achieve Turing completeness can be quite different; Fortran
Fortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
systems would use loop constructs or possibly even goto
Goto
goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use recursion
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
. Turing completeness is an abstract statement of ability, rather than a prescription of specific language features used to implement that ability.
Turing completeness in SQL
SQL
SQL is a programming language designed for managing data in relational database management systems ....
is implemented through advanced standard features, illustrating one reason relatively powerful non-Turing-complete languages are rare: the more powerful the language is initially, the more complex are the tasks to which it is applied and the sooner its lack of completeness becomes perceived as a drawback, encouraging its extension until it is Turing complete.
The untyped lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
is Turing complete, but many typed lambda calculi, including System F
System F
System F, also known as the polymorphic lambda calculus or the second-order lambda calculus, is a typed lambda calculus that differs from the simply typed lambda calculus by the introduction of a mechanism of universal quantification over types...
, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.
Rule 110 and Conway's Game of Life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, both cellular automata
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
, are Turing complete.
Non-Turing-complete languages
Many computational languages exist which are not Turing complete. One such example is the set of regular languageRegular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s, most commonly regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
s, which are generated by finite automata
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata
Pushdown automaton
In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...
and context-free grammar
Context-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
s, which are commonly used to generate parse trees in an initial stage of program compiling
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D
Direct3D
Direct3D is part of Microsoft's DirectX application programming interface . Direct3D is available for Microsoft Windows operating systems , and for other platforms through the open source software Wine. It is the base for the graphics API on the Xbox and Xbox 360 console systems...
and OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...
extensions, or a series of mathematical formulae in a spreadsheet
Spreadsheet
A spreadsheet is a computer application that simulates a paper accounting worksheet. It displays multiple cells usually in a two-dimensional matrix or grid consisting of rows and columns. Each cell contains alphanumeric text, numeric values or formulas...
with no cycles.
In some languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
, whereas Epigram uses dependent type
Dependent type
In computer science and logic, a dependent type is a type that depends on a value. Dependent types play a central role in intuitionistic type theory and in the design of functional programming languages like ATS, Agda and Epigram....
s.
Data languages
Languages such as XMLXML
Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....
, JSON
JSON
JSON , or JavaScript Object Notation, is a lightweight text-based open standard designed for human-readable data interchange. It is derived from the JavaScript scripting language for representing simple data structures and associative arrays, called objects...
, YAML
YAML
YAML is a human-readable data serialization format that takes concepts from programming languages such as C, Perl, and Python, and ideas from XML and the data format of electronic mail . YAML was first proposed by Clark Evans in 2001, who designed it together with Ingy döt Net and Oren Ben-Kiki...
and S-expression
S-expression
S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...
s are not Turing complete because they are only used to represent structured data, not describe computation. These are sometimes referred to as markup language
Markup language
A markup language is a modern system for annotating a text in a way that is syntactically distinguishable from that text. The idea and terminology evolved from the "marking up" of manuscripts, i.e. the revision instructions by editors, traditionally written with a blue pencil on authors' manuscripts...
s, or more properly as "data description languages".
Non-Turing complete languages, especially data languages, are desirable in that they can be manipulated, which, however, also applies to some Turing-complete languages, most notably Lisp and many of its dialects like Scheme. This is codified in the web design principle known as the "Rule of Least Power", which recommends avoiding the use of Turing complete languages, and in fact using the least powerful language that satisfies a task, so that the result data can more easily be reused and transformed.
See also
- Loop (computing)
- Inner loopInner loopIn computer programs, an important form of control flow is the loop. For example, this small pseudo-code program uses two nested loops to iterate over all the entries of an n×n matrix, changing their values so that the matrix becomes an identity matrix: for a in 1..n for b in 1..n ...
- Smn theorem
- Church–Turing thesisChurch–Turing thesisIn computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...
- Computability theoryComputability theory (computer science)Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science...
- Algorithmic information theoryAlgorithmic information theoryAlgorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...
- Chomsky hierarchyChomsky hierarchyWithin the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
- Machines that always halt
- Stephen WolframStephen WolframStephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
's A New Kind of Science- Principle of Computational Equivalence
- Turing tarpitTuring tarpitA Turing tarpit is any programming language or computer interface that allows for a great deal of flexibility in function but is difficult to learn and use because it offers little or no support for common tasks...
- Structured program theoremStructured program theoremThe structured program theorem is a result in programming language theory. It states that every computable function can be implemented in a programming language that combines subprograms in only three specific ways...