Definition
Computation Theory (or Theory of Computation) is the branch of computer science and mathematics that investigates whether and how efficiently problems can be solved using an algorithm on a model of computation. It is traditionally divided into three sub-fields: Automata Theory, Computability Theory, and Computational Complexity Theory.
Why It Matters
It defines what is actually solvable by a machine, preventing wasted effort on mathematically impossible problems.
Core Concepts
- Automata Theory: The study of abstract machines (e.g., Finite State Machines, Pushdown Automata) and the formal languages they can recognize.
- Computability Theory: Focuses on what can be solved by a machine. The Church-Turing Thesis posits that any function that can be computed by an algorithm can be computed by a Turing Machine.
- The Halting Problem: A foundational proof by Alan Turing showing that there are certain problems that no algorithm can ever solve (undecidability).
- Complexity Theory: Classifies problems based on the resources (time and space) required to solve them. Key classes include P (easy to solve) and NP (easy to verify).
- Turing Completeness: A system is Turing complete if it can simulate any Turing machine, meaning it can perform any computation that any other computer can.