A report on Turing completeness

Said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine (devised by English mathematician and computer scientist Alan Turing).

- Turing completeness

35 related topics with Alpha

Overall
A physical Turing machine model. A true Turing machine would have unlimited tape on both sides, however, physical models can only have a finite amount of tape.

Turing machine

7 links

Mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

Mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

A physical Turing machine model. A true Turing machine would have unlimited tape on both sides, however, physical models can only have a finite amount of tape.
The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q4) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.)
Here, the internal state (q1) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)
The "3-state busy beaver" Turing machine in a finite-state representation. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state transition is shown by an arrow. The label (e.g. 0/P,R) near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. 0) followed by a slash /, followed by the subsequent "behaviors" of the machine, e.g. "P print" then move tape "R right". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).
The evolution of the busy beaver's computation starts at the top and proceeds to the bottom.
An implementation of a Turing machine
A Turing machine realization using Lego pieces
Another Turing machine realization

Turing completeness is the ability for a system of instructions to simulate a Turing machine.

The source code for a simple computer program written in the C programming language. The gray lines are comments that help explain the program to humans in a natural language. When compiled and run, it will give the output "Hello, world!".

Programming language

7 links

Any set of rules that converts strings, or graphical program elements in the case of visual programming languages, to various kinds of machine code output.

Any set of rules that converts strings, or graphical program elements in the case of visual programming languages, to various kinds of machine code output.

The source code for a simple computer program written in the C programming language. The gray lines are comments that help explain the program to humans in a natural language. When compiled and run, it will give the output "Hello, world!".
A selection of programming language textbooks; only a few of the thousands available.
Parse tree of Python code with inset tokenization
Syntax highlighting is often used to aid programmers in recognizing elements of source code. The language above is Python.

XSLT, for example, is a Turing complete language entirely using XML syntax.

A human computer, with microscope and calculator, 1952

Computer

7 links

Digital electronic machine that can be programmed to carry out sequences of arithmetic or logical operations automatically.

Digital electronic machine that can be programmed to carry out sequences of arithmetic or logical operations automatically.

A human computer, with microscope and calculator, 1952
The Ishango bone, a bone tool dating back to prehistoric Africa.
The Chinese suanpan (算盘). The number represented on this abacus is 6,302,715,408.
The Antikythera mechanism, dating back to ancient Greece circa 150–100 BC, is an early analog computing device.
A slide rule.
A portion of Babbage's Difference engine.
Sir William Thomson's third tide-predicting machine design, 1879–81
Replica of Konrad Zuse's Z3, the first fully automatic, digital (electromechanical) computer.
Colossus, the first electronic digital programmable computing device, was used to break German ciphers during World War II. It is seen here in use at Bletchley Park in 1943.
ENIAC was the first electronic, Turing-complete device, and performed ballistics trajectory calculations for the United States Army.
A section of the Manchester Baby, the first electronic stored-program computer
Bipolar junction transistor (BJT)
MOSFET (MOS transistor), showing gate (G), body (B), source (S) and drain (D) terminals. The gate is separated from the body by an insulating layer (pink).
Diagram showing how a particular MIPS architecture instruction would be decoded by the control system
Magnetic-core memory (using magnetic cores) was the computer memory of choice in the 1960s, until it was replaced by semiconductor memory (using MOS memory cells).
Hard disk drives are common storage devices used with computers.
Cray designed many supercomputers that used multiprocessing heavily.
Replica of the Manchester Baby, the world's first electronic stored-program computer, at the Museum of Science and Industry in Manchester, England
A 1970s punched card containing one line from a Fortran program. The card reads: "Z(1) = Y + W(1)" and is labeled "PROJ039" for identification purposes.
The actual first computer bug, a moth found trapped on a relay of the Harvard Mark II computer
Visualization of a portion of the routes on the Internet

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.

Lovelace's description from Note G.

Computer program

5 links

Sequence or set of instructions in a programming language for a computer to execute.

Sequence or set of instructions in a programming language for a computer to execute.

Lovelace's description from Note G.
350px
Zuse Z3 replica on display at Deutsches Museum in Munich
Glenn A. Beck is changing a tube in ENIAC.
Switches for manual input on a Data General Nova 3, manufactured in the mid-1970s
A VLSI integrated-circuit die.
IBM's System/360 (1964) CPU wasn't a microprocessor.
Artist's depiction of Sacramento State University's Intel 8008 microcomputer (1972).
The original IBM Personal Computer (1981) used an Intel 8088 microprocessor.
The DEC VT100 (1978) was a widely used computer terminal.
Prior to programming languages, Betty Jennings and Fran Bilas programmed the ENIAC by moving cables and setting switches.
"Hello, World!" computer program by Brian Kernighan (1978)
A computer program written in an imperative language
A diagram showing that the user interacts with the application software. The application software interacts with the operating system, which interacts with the hardware.
A kernel connects the application software to the hardware of a computer.
Physical memory is scattered around RAM and the hard disk. Virtual memory is one continuous block.
NOT gate.
NAND gate.
NOR gate.
AND gate.
OR gate.
A symbolic representation of an ALU.
400x400px
Computer memory map

All present-day computers are Turing complete.

Functional programming

6 links

Programming paradigm where programs are constructed by applying and composing functions.

Programming paradigm where programs are constructed by applying and composing functions.

In 1937 Alan Turing proved that the lambda calculus and Turing machines are equivalent models of computation, showing that the lambda calculus is Turing complete.

Halting problem

5 links

Problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.

Problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run 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.

Gosper's Glider Gun creating "gliders" in the cellular automaton Conway's Game of Life

Cellular automaton

3 links

A cellular automaton (pl.

A cellular automaton (pl.

Gosper's Glider Gun creating "gliders" in the cellular automaton Conway's Game of Life
A torus, a toroidal shape
John von Neumann, Los Alamos ID badge
A cellular automaton based on hexagonal cells instead of squares (rule 34/2)
An animation of the way the rules of a 1D cellular automaton determine the next generation.
Rule 30
Rule 110
Conus textile exhibits a cellular automaton pattern on its shell.
Visualization of a lattice gas automaton. The shades of grey of the individual pixels are proportional to the gas particle density (between 0 and 4) at that pixel. The gas is surrounded by a shell of yellow cells that act as reflectors to create a closed space.

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.

Lambda calculus

5 links

Formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

Formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

Lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any Turing machine.

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).

Algorithm

4 links

Algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

Algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).
Ada Lovelace's diagram from "note G", the first published computer algorithm
Logical NAND algorithm implemented electronically in 7400 chip
Flowchart examples of the canonical Böhm-Jacopini structures: the SEQUENCE (rectangles descending the page), the WHILE-DO and the IF-THEN-ELSE. The three structures are made of the primitive conditional GOTO (IF test THEN GOTO step xxx, shown as diamond), the unconditional GOTO (rectangle), various assignment operators (rectangle), and HALT (rectangle). Nesting of these structures inside assignment-blocks result in complex diagrams (cf. Tausworthe 1977:100, 114).
The example-diagram of Euclid's algorithm from T.L. Heath (1908), with more detail added. Euclid does not go beyond a third measuring and gives no numerical examples. Nicomachus gives the example of 49 and 21: "I subtract the less from the greater; 28 is left; then again I subtract from this the same 21 (for this is possible); 7 is left; I subtract this from 21, 14 is left; from which I again subtract 7 (for this is possible); 7 is left, but 7 cannot be subtracted from 7." Heath comments that "The last phrase is curious, but the meaning of it is obvious enough, as also the meaning of the phrase about ending 'at one and the same number'."(Heath 1908:300).
A graphical expression of Euclid's algorithm to find the greatest common divisor for 1599 and 650.
"Inelegant" is a translation of Knuth's version of the algorithm with a subtraction-based remainder-loop replacing his use of division (or a "modulus" instruction). Derived from Knuth 1973:2–4. Depending on the two numbers "Inelegant" may compute the g.c.d. in fewer steps than "Elegant".
Alan Turing's statue at Bletchley Park

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.

Konrad Zuse in 1992

Konrad Zuse

3 links

German civil engineer, pioneering computer scientist, inventor and businessman.

German civil engineer, pioneering computer scientist, inventor and businessman.

Konrad Zuse in 1992
Zuse Z1 replica in the German Museum of Technology in Berlin
Plaque commemorating Zuse's work, attached to the ruin of Methfesselstraße 7, Berlin
Statue of Zuse in Bad Hersfeld
Z64 Graphomat plotter
An elementary process in Zuse's Calculating Space: Two digital particles A und B form a new digital particle C.
Zuse Memorial in Hünfeld, Hessen
Zuse's workshop at Neukirchen (photograph taken in January 2010)
Magnetic drum storage inside a Z31 (which was first displayed in 1963).

His greatest achievement was the world's first programmable computer; the functional program-controlled Turing-complete Z3 became operational in May 1941.