Turing completeness

In computability theory, a system of data-manipulation rules (such as a model of computation, 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 (devised by English mathematician and computer scientist Alan Turing). This means that this system is able to recognize or decode other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete.

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. A universal Turing machine can be used to simulate any Turing machine and by extension the purely computational aspects of any possible real-world computer.

To show that something is Turing-complete, it is enough to demonstrate that it can be used to simulate some Turing-complete system. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete.

Non-mathematical usage

In everyday language, the words "Turing-complete" and "Turing-equivalent" mean that any regular computer or computer language can act like any other regular computer or computer language. This idea helps us understand concepts like virtualization and emulation.

Real computers we use today work in ways that are similar to a special kind of machine called a single-tape Turing machine. But because real computers have limited space and time, they can only do certain tasks. The idea of a "universal computer" is one that can do any task if given enough time and space.

Formal definitions

In computability theory, we talk about how powerful different computing systems can be, like programming languages or abstract machines.

A system is called Turing-complete if it can perform any calculation that a special kind of machine, called a universal Turing machine, can do. This means it is very powerful in terms of what it can compute.

If a Turing-complete system can compute exactly the same set of problems as a Turing machine, it is called Turing-equivalent. This means it can both perform and be performed by the universal Turing machine. Usually, when people talk about a system being universal, they mean it can handle all tasks that a Turing-complete system can. Sometimes, a system might be called "weakly universal" if it needs a special rule to match the abilities of a Turing machine, like allowing endless input.

History

Turing completeness is important because any real computing device can be simulated by a universal Turing machine. The Church–Turing thesis says that a universal Turing machine can perform any calculation that any other programmable computer can, even if it takes more time or effort.

Charles Babbage designed the analytical engine in the 1830s, which would have been the first Turing-complete machine if it had been built. However, machines from that time, like adders and multipliers, could not perform conditional branching and were not Turing-complete.

Later, mathematicians like Leopold Kronecker and David Hilbert worked on ideas about what can be calculated. Kurt Gödel showed that certain problems could not be solved by machines. In 1941, Konrad Zuse built the Z3 computer, which was later found to be Turing-complete in theory, though it did not support conditional branching at the time. The first computer that could actually perform conditional branching was the ENIAC in 1946.

Computability theory

Computability theory uses models of computation to study problems and decide if they can be solved by computers. One big idea in this theory is that some problems are impossible for computers to solve if we don’t know how long it will take.

A famous example is called the halting problem. Imagine trying to make a tool that can look at any computer program and some data, and tell us if the program will ever stop running or keep going forever. While we can make such a tool work for some programs, it’s impossible to make it work for all programs. This means we can’t always know what a program will do in every case.

This makes it hard to protect programs from running forever without stopping. One way to help is to set a time limit for how long a program can run (timeout) or to use simpler rules for repeating steps. But even with these limits, there are some problems that can only be solved by more powerful computer languages. For example, some special math problems, like those shown using Cantor's diagonal argument, can’t be solved by programs that are designed to always finish and stop.

Turing oracles

Main article: Oracle machine

A computer that can read an endless strip of information might be more powerful than a regular Turing machine. For example, this strip could hold the answer to very difficult problems that normal computers cannot solve. This special strip of information is called a Turing oracle. Even if the Turing oracle has random information, it is still not something a normal computer can fully understand or work with, because there are only a limited number of ways to compute but an endless number of possible oracles. This means a computer with a random Turing oracle can handle tasks that a normal Turing machine cannot.

Digital physics

See also: Church–Turing thesis § Philosophical implications

Scientists believe that all the rules that govern how our world works can be understood step by step using a regular computer. This idea, called digital physics, suggests that the universe itself can be studied and calculated using the same methods as a powerful computer. If this is true, it means we could never build a computer that is more powerful than the most advanced kinds we already know about.

Examples

Computational systems that are Turing-complete are used mainly in theoretical computer science. They are kept simple to help understand the limits of what computers can do. Some examples include automata theory, formal grammar, formal language, lambda calculus, Post–Turing machines, and process calculus.

Most programming languages, whether common or unusual, are Turing-complete. This includes general-purpose languages like procedural programming languages such as C and Pascal, object-oriented languages such as Java and Smalltalk, and multi-paradigm languages such as Ada, C++, and Python. Other languages, like functional languages such as Lisp and Haskell, and logic programming languages such as Prolog, are also Turing-complete.

Some systems, like Microsoft Excel and certain video games such as Minecraft and Baba Is You, are Turing-complete by accident rather than design. Even some biological systems, like chemical reaction networks, have been shown to perform like Turing machines.

Non-Turing-complete languages

Many programming languages are not Turing-complete, meaning they cannot simulate every possible computation. One example is the set of regular languages, which are created using regular expressions and recognized by finite automata. Another example is the group of pushdown automata and context-free grammars, used in the early steps of compiling programs.

Some programming languages, like Charity and Epigram, are designed to only allow functions that always finish and stop. The LOOP language is made to compute only certain types of functions. Even though lambda calculus can be Turing-complete, its simpler version, simply typed lambda calculus, is not.