computability
Sign in to saveComputability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
~19 min read
Encyclopedic overview
14 sectionsContents
- Problems
- Power of automata
- Power of finite-state machines
- Power of pushdown automata
- Power of Turing machines
- The halting problem
- Beyond recursively enumerable languages
- Concurrency-based models
- Stronger models of computation
- Infinite execution
- Oracle machines
- Limits of hyper-computation
- See also
- References
Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. 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.
Excerpted from Wikipedia’s “computability” article, available under the CC BY-SA 4.0 licence.