- tags
- Computability theory
A function on the natural numbers can be computed effectively if and only if it can be computed by a Turing Machine (or any equivalent computational model).
Implications for Zuse’s thesis
An interesting implication of the Church-Turing thesis is any Turing-complete computational model could in theory be “computing” our Universe. However, the constant overhead of running this algorithm is very different from one model to another. There must be an optimal or close to optimal computational model for simulating life processes and it seems from everyday observation that it should be inherently parallel.