Turing completeness

In computability theory, a system of rules for working with data (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is Turing-complete if it can act like a special kind of machine made up by a mathematician named Alan Turing. This means the system can work with any set of rules.

Turing completeness shows how powerful a set of rules is. Almost all programming languages we use today are Turing-complete.

Two computers are Turing equivalent if each can act like the other. The Church–Turing thesis says that any job that can be done by following steps can be done by a Turing machine. A universal Turing machine can act like any Turing machine and most real computers.

To prove something is Turing-complete, we only need to show it can act like another Turing-complete system. Real computers have limited memory, but most programming languages are still Turing-complete if we ignore this limit.

Non-mathematical usage

In everyday language, "Turing-complete" and "Turing-equivalent" mean that any normal computer or computer language can act like any other normal computer or language. This idea helps us understand things 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 learn how powerful different computing systems can be, like programming languages or special machines.

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

If a Turing-complete system can solve the same problems as a Turing machine, it is called Turing-equivalent. This means it can both do and be done by the universal Turing machine. Usually, when people say a system is universal, they mean it can handle all tasks a Turing-complete system can. Sometimes, a system might be called "weakly universal" if it needs a special rule to match a Turing machine, like needing 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 do any calculation that any other programmable computer can.

Charles Babbage designed the analytical engine in the 1830s. This would have been the first Turing-complete machine if it had been built. But machines from that time could not do 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 some problems could not be solved by machines. In 1941, Konrad Zuse built the Z3 computer. This was Turing-complete in theory, but it could not do conditional branching. The first computer that could do conditional branching was the ENIAC in 1946.

Computability theory

Computability theory uses models of computation to study problems and see if they can be solved by computers. One big idea is that some problems are too hard 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). 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 a very long strip of information might be more powerful than a regular computer. This strip could have answers to very hard problems that normal computers cannot solve. This special strip 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 use. This is because there are only a limited number of ways to compute but an endless number of possible oracles. So, a computer with a random Turing oracle can do tasks that a normal computer cannot.

Digital physics

See also: Church–Turing thesis § Philosophical implications

Scientists think that all the rules that make our world work can be understood step by step using a normal computer. This idea, called digital physics, suggests that the universe can be studied and figured out using the same ways as a powerful computer. If this is true, it means we could never make a computer better than the best ones we already have.

Examples

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

Most programming languages are Turing-complete. This includes languages like procedural programming such as C and Pascal, object-oriented languages such as Java and Smalltalk, and languages like 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. Even some biological systems can act like Turing machines.

Non-Turing-complete languages

Many programming languages are not Turing-complete. This means they cannot do every kind of calculation.

One example is the set of regular languages. These are made using regular expressions and recognized by finite automata.

Another example is the group of pushdown automata and context-free grammars. These are used in the first steps of compiling programs.

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