Universal Computation | Turing Completeness
A model of computation is universal/turing complete if it can simulate any other model of computation. In other words, it can compute any function that is computable by any means whatsoever.
Link to originalAll reasonable models of computation are equivalent in power. They can all compute exactly the same set of functions - the computables
This includes:
- turing machines (universal turing machine)
- lambda calculus
- general recursive functions
- modern programming languages
- certain cellular automata (like rule 110)