Turing completeness

Last updated on Oct 25, 2021 learning, zettel, zettelkasten

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)

References

https://stackoverflow.com/questions/3492188/what-are-the-practical-limitations-of-a-non-turing-complete-language-like-coq

Like this post? Subscribe for more.