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.
Wikidata facts
Show 1 more fact
- ACM Classification Code (2012)
- 10003754
Sources (2)
via Wikidata · CC0
~19 min read
Article
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.