Method
Computability
Overview
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.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Related ideas
- Automata theory
- Formal language
- Grammar
- Computability theory
- Foundations of mathematics
- Lambda calculus
- Mathematical logic
- Natural number
- Number theory
- Theory of computation
- Turing machine
- Computer science
- Context-free grammar
- Church–Turing thesis
- Algorithm
- Decision problem
- Halting problem
Place in the tradition
Part of Ontology.