Theory of computation
Builds on Model of computationDecision problem
Definition
The theory of computation is the branch of mathematics and theoretical computer science that studies the following questions about a model of computation.
- Which decision problems and functions can be solved by a machine of the model at all; this is computability theory.
- How many resources, such as time and memory, a solution needs; this is computational complexity theory.
- What restricted machines, such as finite automata, can recognise; this is automata theory.
Remarks
Example: the result that no Turing machine solves the halting problem belongs to the theory of computation, in its first part. Non-example: the design of a faster processor chip is not part of the theory, because it concerns physical hardware and not what an abstract model can compute. The answers to the first question do not depend on the choice among the usual models, since these are all equivalent in power. The answers to the second question depend on the model, but only up to polynomial factors among the usual deterministic models.
Reading path
To understand this page from the ground up, read these 3 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Decision problem concept
- Model of computation concept
- Theory of computation definition
Further reading
About this page
| Tag | QXZ8X4CWGS |
|---|---|
| URI | m2://QXZ8X4CWGS |
| Kind | definition |
| Writing | W0 stub |
| MSC | 68Q01, 03D10 |
| Defines | Theory of computation |
| Uses | Model of computation, Decision problem |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.