Turing-Completeness

Turing-completeness refers to the ability to solve computational problems, thus simulating a Turing machine. That is, at a high-level, Turing-complete systems are ones in which a program can be ran and an answer returned. This term may refer to physical entities, such as computers, or virtual entities, such as programming languages. This concept, as illustrated in the Church-Turing thesis, was pioneered by computer scientist Alan Turing in the early twentieth century. Specifically, according to this thesis, a Turing-complete system must be able to:

  • Use infinite memory and make decisions based on its memory
  • Run programs for an infinite amount of time
  • Have random access memory
  • Simulate another Turing-machine

With regard to blockchain, the most notable example of Turing-complete technology is the Ethereum Virtual Machine, upon which smart contracts written in the Turing-complete Solidity programming language operate. Other Turing-complete smart contract platforms include EOS, Tezos and Edgeware.