Turing completeness
October 25, 2021
- refers to the ability to simulate any turing machine (basically perform any computation)
- with this power, comes great resposibility (undecidability, halting problem)
When do you want and not want it?
- if you don’t need arbitrary features, limiting your feature set (turing completeness), can improve security and predictability of your language
- main features: arbitrary recursion, dynamic memory allocation (
malloc), arbitrary loops (while) - instead of static memory planning,
More
- in the EVM: gas limits memory and computation
- Learn more Coq (turing-incomplete)