Theory of Computation
 |
|
The theory of computation is the branch of mathematics that studies what types of tasks are theoretically possible with computing machines. It is also concerned with the relative difficulty and complexity of these tasks. Mathematical models for computers such as Turing machines and finite automata are essential tools.
Theory of computation is a college-level concept and course.
Prerequisites
| Cellular Automaton: | A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. |
| Turing Machine: | A Turing machine is a theoretical computing machine that serves as an idealized model for mathematical calculation. |