A model of computation is a system of instructions for manipulating information. Different models may have different capabilities, such as possessing different kinds of memory, or doing multiple computations in parallel. Models that are Turing-complete may simulate any other model, given some restrictions; the model to be simulated must not be unrealistically powerful. In spite of this redundancy, many models of computation are in use, as some models are more convenient than others when analyzing particular situations. An incomplete list: - Turing machines - A finite-state automaton attached to a tape with squares that contain symbols - the most well-known model. devised by Alan Turing. - It's pretty fun to write algorithms using Turing machines; see [[Simulating Turing machines]] - Cellular automata - infinite n-dimensional lattice, where lattice points have states that may change at each timestep - most famous example: the [Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) - Invented by von Neumann - Term rewriting - take some data structure, like a string or a tree, and iteratively match and replace sub-structures - Examples: [lambda calculus](https://en.wikipedia.org/wiki/Lambda_calculus), [SKI combinator calculus](https://en.wikipedia.org/wiki/SKI_combinator_calculus), [tag system](https://en.wikipedia.org/wiki/Tag_system) - Actor model - Independent computers pass messages over channels asynchronously - resembles the Internet and the brain (resembles! I'm not making any serious claim that they're related) - Erlang uses this model