| • Science | • People | • Locations | • Timeline |
See the article on theory of computation for a chart showing which classes of problems are subsets of other classes.
Not all problems can be solved. An undecidable problem is one that cannot be solved by any algorithm, even given unbounded time and memory. Many undecidable problems are known. For example, the Entscheidungsproblem (German for "decision problem") is this: given a statement in first-order predicate calculus, decide whether it is universally valid. Church and Turing independently proved this is undecidable. The halting problem is: given a program and inputs for it, decide whether it will run forever or will eventually halt. Turing proved this is also undecidable. A computable number is a real number which can be approximated to any arbitrary degree of accuracy by an algorithm. Turing proved that almost all numbers are uncomputable. Chaitin's constant is an uncomputable number, even though it is well defined.
The languages that are accepted by a Turing machine are exactly those that are generated by formal grammars. The lambda calculusThe lambda calculus is a formal system designed to investigate function definition, function application, and recursion. It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s; Church used the lambda calculus in 1936 to give a negative an is a way of defining functions. The functions that can be computed in the lambda calculus are exactly those that can be computed by a Turing machine. These three formulations, Turing machines, formal grammars, and the lambda calculus all look very different, and were all developed by different people. Yet they are all equivalent, and have the same problem-solving power. This is generally taken as evidence for the Church-Turing thesisIn the computability theory the Church-Turing thesis Church's thesis Church's conjecture or Turing's thesis named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, like computers, and what kind of alg, which is the claim that our intuitive notion of an algorithm or an effective procedure is captured by the mathematical definition of a Turing machine.
Electronic computers, and even quantum computerMolecule of alanine used in NMR implementation of error correction. Qubits are implemented by spin states of carbon atoms. A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superps, are exactly equivalent to Turing machines, if they have access to an unbounded supply of memory. As a corollary, all implementable programming languagesAn alternate rewrite has been has been. Please refer to it for large rewrites. A programming language or computer language is a standardized communication technique for expressing instructions to a computer. It is a set of syntactic and semantic rules use are at best equivalent in power to a Turing machine (in practice, a very few are less powerful). Such languages are said to be Turing-complete. Systems equivalent to a Turing machine include:
The last three examples use a slightly different definition of accepting a language. They are said to accept a string if any computation accepts (for non-deterministic), or most computations accept (for probabilistic and quantum). Given these definitions, those machines have the same power as a Turing machine for accepting languages.