Blockchains are distributed ledgers that store and maintain a list of ordered transaction records, known as blocks. In order to maintain these records, blockchains use a system called consensus mechanisms, which involve network participants mining (Proof of Work) or staking their coins (Proof of Stake). Aside from storing and providing data, blockchains also host a series of executable codes, known as “smart contracts”, which are programs that execute when certain conditions are met. Each blockchain’s smart contract capability differs based on its Turing structure (i.e., if it is Turing complete or non-Truing complete). In this article, we’ll take a deep look at blockchains that are Turing complete and non-Turing complete.
Let’s begin with the basics
To effectively understand the concept of Turing complete (and non-Turing complete), we’ll need to refer to Alan Mathison’s Turing machine. In 1936, Alan M. Turing hypothesised that the Turing machine was an abstract mathematical tool that could implement any computer algorithm (regardless of its difficulty) as long as it was given enough time and the necessary instructions to act.
To be clear, the Turing machine is not a physical item but an idealized mathematical model (that gave birth to the term "Turing complete"). Alan envisaged the machine having an infinite length of tape divided into boxes, where each box would have an instruction written in binary code (1 and 0), which could be interpreted by the machine. Each time an instruction is sent to the machine, it carries out the order by overwriting the old one with a new symbol in the same box. Then the machine’s state is updated. The theory of the Turing machine sets the standard for modern computers and programming languages like Python, Java, C++, Ruby etc
In context, a system is Turing complete when it can solve or execute any computational problem or instruction. On the other end, a non-Turing system would be one that has limited functionality and can only solve basic problems. To better understand the contrast, think of a pocket calculator as a non-Turing complete machine because it is limited to solving a limited set of mathematical problems. However, your smartphone can be tagged as a Turing-complete machine as it has the ability to perform the same task as a calculator including more complex ones. Yet it's crucial to remember that the pocket calculator was designed with one single function in mind, making it a more dependable and effective choice than a smartphone, which could freeze, display irking ads, or get a bug.
Turing Complete blockchains
Regarding blockchain technology, a blockchain is said to be Turing complete when it is built on a programming language that allows developers to deploy complex smart contracts and decentralized applications (dapps). Ethereum is a perfect example of a Turing complete blockchain, with its smart contracts written in Solidity, which is a Turing complete programming language. Additionally, Ethereum’s smart contracts are executed on the EVM, a Turing complete machine that is the general overseer of all smart contracts running on the Ethereum blockchain. Being Turing complete simply means developers can explore the possible outcomes of writing and deploying complex smart contracts, which is one of the foundations of decentralized finance (DeFi) as we know it today.
The strength and glamour of a Turing complete blockchain lie in its programmable versatility, but within this lies its vulnerability. Smart contracts that are deployed on Turing complete public blockchains are sometimes difficult to audit, and if an error is detected earlier by a bad actor, it can be exploited, therefore leading to contract hacks and liquidity syphoning. Among the numerous hacking incidents that have occurred, the most significant would be TheDAO, a smart contract on Ethereum built to act as a fundraising platform in 2016. The team failed to observe a weak point in their code, and it was exploited by hackers who discovered it earlier, resulting in a loss of over $50 million in investor funds. In a bid to resolve the problem, the Ethereum Foundation decided to fork the blockchain, and investors were refunded via the Withdraw DAO. But TheDAO is not the only smart contract that has been exploited; other platforms that have suffered hacks without making provisions to refund investors have succeeded in eternally separating investors from their funds.
Non-Turing complete blockchains
Unlike Turing complete blockchains, these are simpler in nature; this is because they can only execute simple smart contracts. Bitcoin is a non-Turing complete blockchain, and its smart contracts are written in the Script programming language. Script is a stack-based programming language that enables the creation of simple and conditional smart contracts.
Regardless of its inability to support complex smart contracts, a notable pro of non-Turing blockchains is the fact that they offer more security and make it easier to audit code effectively; these are crucial factors to consider, especially when liquidity is on the line.
Is Decred a Turing complete blockchain?
Decred is not a Turing complete blockchain because it uses a scripting system called txscript to write smart contracts. Txscript is described as a simple, stack-based, Forth-like programming language that can be used to dictate the conditions attached to a transaction. Similar to Bitcoin, it can also implement time locks that prevent the spending of $DCR until a preferred time.
As a stack-based language, txscript uses operation codes (opcodes) to pop items from the stack, perform calculations on them, and push the result back onto the stack, similar to a stack data structure. Each script runs from left to right, and as it runs, it makes use of the stacks to store values.
Being a non-Turing complete programming language means it lacks complex structures and functionality. While this can be considered a limitation, it does come with key benefits. one of which is its immunity to the “halting problem" —a challenge in determining whether a program will run to completion or halt (i.e., terminate at any point). This is a common problem with Turing complete because of its complexity, it becomes uncertain if a smart contract is reliable enough to execute completely or enter an infinite loop. Additionally, the complexity of contracts is limited, which allows for easy auditing and thorough testing.
Understanding the blockchain you choose to invest in or base your project on is essential. In summary, being Turing complete denotes a system's strength, complexity, and potential security risk. A non-Turing complete system, on the other hand, supports simplicity.