Computability
Jump to navigation
Jump to search
See: Turing Machine, Computability Theory.
References
2009
- http://en.wikipedia.org/wiki/Computability
- Computability refers to the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
- The most widely-studied form of computability is Turing computability, which is computability via a Turing machine. However, many other forms of computability are studied as well. Computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation.
- Apart from the bare question of what problems can be effectively solved, computer scientists are also interested in the resources, such as time and memory, that are required to solve problems using different models of computation. Models of parallel computation, for example, are of interest for their speed of computation, even though any problem solvable by parallel computation is also solvable by non-parallel computation. The field of computational complexity theory is devoted to the study of the resources used during computations.