Computational Models

Computational models in the order of increasing computing power they wield.

1. Finite State Machines (FSM)
2. Context free languages
3. Turing Machines
4. Undecidables

Finite State Machines (FSM)

To solve certain set of problems, e.g. is there a zero at the end of string.

Context free languages

A set of strings is a language. More powerful than FSM. Can tell whether a given set of strings is a valid program.

Turing Machines

Anything that can be computed can be computed with a Turing Machine. Includes P and NP problems.

Undecidables

Problems that cannot be solved with a computer.