Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

computability theory





The part of the theory of computation that deals with problems that are solvable by algorithms or – what amounts to the same thing – by Turing machines. Computability theory is concerned with four main questions: What problems can Turing machines solve? What other systems are equivalent to Turing machines? What problems require more powerful machines? What problems can be solved by less powerful machines?

Not all problems can be solved computationally. An undecidable problem is one that can't be solved by any algorithm, no matter how much time, processing speed, or memory is available. Many examples are known, one of the most famous of which is the halting problem.


Related entries

   • cellular automaton
   • quantum computer


Related category

   • COMPUTERS, ARTIFICIAL INTELLIGENCE, AND CYBERNETICS