A computational model (commonly called a model of computation) is a theoretical framework that applies resource constraints in order to reason useful properties of algorithms that run in said models.
Algorithms require resources to solve computational problems. These resources include:
- Time: An algorithm takes time to solve a problem. Time complexity is a useful measure of how much time an algorithm.
- Storage: An algorithm usually stores some data (known as caching) when solving a problem. This can be either in the form of data structures, or memoization. For example, a in-place sorting algorithm, solves the problem of sorting an array with lesser storage than a sorting algorithm that is not in-place.
- Randomness
- Input Access
- Quantum Entanglement (Used by quantum computers)
- Time travel#tosee
However, we don’t an infinite amount of these resources! We certainly don’t have infinite time and storage. A computational model is then a set of resource constraints, such as limiting time to not be infinite. Theoretical computer science studies the trade-offs between using different types of these models.
An automaton is incomplete if its transition function is not surjective?
- Finite State Automata: Memory restriction (no memory)
- (Non-deterministic) Pushdown Automata: Memory access restriction (can only access memory in LIFO order)
- Turing Machine
Resources
- https://www.automataverse.com/simulator - Automaton Simulator