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

Also on this site:

Encyclopedia of Alternative Energy & Sustainable Living
Encyclopedia of History

BACK TO TOP