What does it mean that Ethereum is "turing complete"

  • People often say that Ethereum is a "turing complete" blockchain, or that it comes with a built-in "turing complete" programming language. What does this mean, and why is it an important feature for Ethereum?

    Some people say Ethereum is not turing complete, because a programm for example can't not run forever, due to gas- and block gas limits.

  • It essentially means you can write programs (contracts) that can (for the most part) solve any reasonable computational problem.

    Using Solidity and Serpent you have the ability to perform looping and branching statements as well as local state storage. This functionality is important to have in order to implement most non-trivial computer programs.

    Because the Ethereum VM is turing complete, I can technically implement logic in say Python and translate to solidity if I want.

    Turing completeness is important for Ethereum smart contracts because you have the ability to implement sophisticated logic.

  • Alan Turing was a mathematician which basicly invented the computer without building one* back in the 1930ies, the so called turing machine.

    It was a mathematical concept of a machine which could calculate anything assumed you have unlimited memory available.

    Turing-completeness therefore refers to any device or system which in theory can calculate everything assuming enough memory is available. And since software is just programmed, and programming is just chaining mathematic statements, everything can be implemented in a turing complete environment.

    The Ethereum blockchain is basicly a distributed turing machine.

    *) On a side note, the first built computer was the Zuse Z1 by Konrad Zuse which was working without electricity.

    Technically, a Turing machine can't compute *everything*, see for example https://en.wikipedia.org/wiki/Chaitin%27s_constant

  • A Turing machine can compute anything that is computable, given enough physical resources.

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM