The execution of an algorithm.
- Input is given
- A step-by-step procedure is followed
- An output is produced
Each step must be an operation that the computer model can perform.
For the precise reasoning purpose, computers are defined as abstract mathematics objects. They are simpler than real computers; but as powerful as real computers.
Models of Computation
Different machines recognize different classes of languages.
- Finite Automata
Recognize regular languages - Pushdown Automata
Recognize context-free languages - Linear Bounded Automata
Recognize context-sensitive languages - Turing Machines
Recognize recursively enumerable languages