Turing completeness

Turing-completeTuring completeuniversalTuring equivalentcomputationally universalTuring equivalenceTuring-equivalentrunning a software programTuring powerfuluniversal computation
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.wikipedia
308 Related Articles

Programming language

programming languageslanguagedialect
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.
XSLT, for example, is a Turing complete language entirely using XML syntax.

Cellular automaton

cellular automataCACell games (cellular automaton)
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine. Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.
In the 1980s, Stephen Wolfram engaged in a systematic study of one-dimensional cellular automata, or what he calls elementary cellular automata; his research assistant Matthew Cook showed that one of these rules is Turing-complete.

Turing machine

deterministic Turing machineTuring machinesuniversal computer
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.
Turing completeness is the ability for a system of instructions to simulate a Turing machine.

Analytical Engine

Analytic EngineBabbage engineBabbage machine
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.
The Analytical Engine incorporated an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory, making it the first design for a general-purpose computer that could be described in modern terms as Turing-complete.

Konrad Zuse

ZuseZuse, KonradZuse KG
In 1941 Konrad Zuse completed the Z3 (computer), the first working Turing-complete machine; this was the first digital computer in the modern sense.
His greatest achievement was the world's first programmable computer; the functional program-controlled Turing-complete Z3 became operational in May 1941.

One instruction set computer

OISCone machine instructionSubtract and branch if negative
For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction; see one instruction set computer) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of data items).
In a Turing-complete model, each memory location can store an arbitrary integer, and – depending on the model – there may be arbitrarily many locations.

Computer

computerscomputer systemdigital computer
The Church–Turing thesis states that this is a law of mathematics – that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can.
The Engine incorporated an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory, making it the first design for a general-purpose computer that could be described in modern terms as Turing-complete.

Algorithm

algorithmsalgorithm designcomputer algorithm
A related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The Church–Turing thesis conjectures that any function whose values can be computed by an algorithm can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine.
But Minsky shows (as do Melzak and Lambek) that his machine is Turing complete with only four general types of instructions: conditional GOTO, unconditional GOTO, assignment/replacement/substitution, and HALT.

Halting problem

always terminatesavoid the halting problemdetect non-terminating computations
The classic example is the halting problem: create an algorithm which takes as input (a) a program in some Turing-complete language, and (b) some data to be fed to that program; and which determines whether the program, operating on the input, will eventually stop or will continue forever.
The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine.

Computer program

programprogramscomputer programs
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.
In 1936, Alan Turing introduced the Universal Turing machine—a theoretical device that can model every computation that can be performed on a Turing complete computing machine.

Universal Turing machine

universaluniversal machineuniversality
A universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer.
Minsky goes on to demonstrate Turing equivalence of a counter machine.

Alan Turing

TuringAlan M. TuringAlan Mathison Turing
The concept is named after English mathematician and computer scientist Alan Turing.

Primitive recursive function

primitive recursiveprimitive recursionprimitive recursive functions
In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions.
Adding unbounded loops (WHILE, GOTO) makes the language partially recursive, or Turing-complete; Floop is such, as are almost all real-world computer languages.

Lambda calculus

beta reductionλ-calculusuntyped lambda calculus
The untyped lambda calculus is Turing-complete, but many typed lambda calculi, including System F, are not.
Lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any Turing machine.

Z3 (computer)

Z3Zuse Z3Z3 computer
In 1941 Konrad Zuse completed the Z3 (computer), the first working Turing-complete machine; this was the first digital computer in the modern sense.
The Z3 was demonstrated in 1998 to be, in principle, Turing-complete.

Church–Turing thesis

Church-Turing thesisChurch's thesisTuring's Thesis
The Church–Turing thesis states that this is a law of mathematics – that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can. A related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The Church–Turing thesis conjectures that any function whose values can be computed by an algorithm can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine.
All these contributions involve proofs that the models are computationally equivalent to the Turing machine; such models are said to be Turing complete.

Post–Turing machine

Formulation 1Post machinePost system
A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below.

Rule 110

Rule 110 cellular automaton
Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.
Like Life, Rule 110 is known to be Turing complete.

Lisp (programming language)

LispLisp programming languageLisp 1.5
He showed that with a few simple operators and a notation for functions, one can build a Turing-complete language for algorithms.

Charles Babbage

BabbageBabbage, CharlesBabbage engines
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.
It would have been the first mechanical device to be, in principle, Turing-complete.

XSLT

XSL TransformationsExtensible Stylesheet Language TransformationsXSL Transformation
Although XSLT is designed as a special-purpose language for XML transformation, the language is Turing-complete, making it theoretically capable of arbitrary computations.

Kurt Gödel

GödelGödel, KurtGodel, Kurt
These rules were proved by Kurt Gödel in 1930 to be enough to produce every theorem.
The book partly explores the ramifications of the fact that Gödel's incompleteness theorem can be applied to any Turing-complete computational system, which may include the human brain.

Esoteric programming language

esotericPiettoy language
Their usual aim is to remove or replace conventional language features while still maintaining a language that is Turing-complete, or even one for which the computational class is unknown.

Conway's Game of Life

Game of LifeConway's LifeConway’s Game of Life
Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.
This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete.

Prolog

SICStus PrologProlog IISICStus
Pure Prolog is based on a subset of first-order predicate logic, Horn clauses, which is Turing-complete.