Computability theory

Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. Computability theory addresses four main questions:

Related Topics:
Theory of computation - Problems - Algorithms - Turing machines

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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?

See the article on theory of computation for a chart showing which classes of problems are subsets of other classes.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Computability theory: What problems can Turing machines solve? ►