What is Turing-Complete?

Nov 1, 2023

Consider the humble pocket calculator and home computer. Between the two, which gadget is more functional? The obvious answer is the home computer, as it can run programs for a multitude of computational problems — this makes it Turing complete. As for the calculator, it’s only equipped to handle a limited range of mathematical operations and is thus considered Turing incomplete.

As the above illustration demonstrates, Turing completeness refers to the extent of a system’s ability to execute any computational task. The more computational functions a system is able to perform, the more “Turing complete” it becomes. 

Turing completeness has been applied to the world of blockchain to assess the capabilities of any given blockchain. Between Bitcoin and Ethereum, for example, Ethereum is Turing complete as it enables developers to write multifaceted programs in Solidity and run them on the Ethereum Virtual Machine (EVM). 

This is different from Bitcoin, whose underlying Script programming language was intentionally designed as a non-Turing complete system that prevents it from executing complex, conditional smart contracts.

This article will walk you through the concept of Turing completeness and how it directly influences the range and complexity of tasks that can be executed on the blockchain.

The History of Turing Complete Systems

As a concept, Turing completeness is rooted in the early days of theoretical computer science, long before the advent of today’s sophisticated computers. 

In 1936, British mathematician and logician Alan Turing published a paper introducing a conceptual framework for a machine capable of executing an arbitrary set of coded instructions. This hypothetical device later came to be known as the Turing machine.

The Turing machine was originally imagined as having an infinite tape, segmented into boxes. Each box contains a simple instruction, coded as a one or a zero. The machine reads these instructions sequentially before replacing the original symbol with a new one, also either a one or a zero. The machine then updates its internal state, which represents a snapshot of its computational process at a given moment.

You can view Turing's hypothetical machine as the prototype of the programmable computer, paving the way for the future development of universal, programmable computers. In today's computing landscape, Turing complete systems are ubiquitous, with the term itself used as a benchmark to gauge a system's computational capabilities.

Ethereum: The First Turing Complete Blockchain

Ethereum was the first blockchain platform to achieve Turing completeness, expanding the realm of possibilities in blockchain technology. This innovative platform allows for the programming of smart contracts and decentralized applications (dApps).

Ethereum’s  Turing completeness comprises two key elements:

  • Solidity, the programming language used for building smart contracts on Ethereum, is Turing complete. It is a general-purpose language tailored specifically for the Ethereum ecosystem.
  • The Ethereum Virtual Machine (EVM), responsible for executing these smart contracts, is also Turing complete.

The EVM's architecture enables it to handle an expansive variety of smart contracts, even those with functionalities yet to be envisioned. This flexibility propelled Ethereum into a revolutionary phase, bringing blockchain technology from a niche utility to a versatile platform with nearly limitless applications.

Practical Limitations to Ethereum’s Turing Completeness

While Ethereum's Turing completeness is revolutionary, it's essential to acknowledge the platform's practical constraints. Theoretically, Turing completeness posits that a system can run any computation, given infinite time and resources. However, in the real-world blockchain environment, each Ethereum transaction consumes "gas," a unit that measures the computational work involved. Should a smart contract enter an infinite loop—a situation theoretically possible in a Turing complete system—it would eventually deplete its gas reserves.

This limitation is intentional. Infinite loops could cripple a public blockchain network, which operates on finite computational resources. Consequently, each transaction on Ethereum mandates a gas limit, specifying the maximum computational effort assignable to that operation. If a transaction fails to complete within this limit, it's automatically terminated.

Moreover, the vast majority of Ethereum smart contracts rarely utilize the full breadth of Turing completeness, including features like recursive loops.

Drawbacks of Turing Completeness in Blockchain

The infinitive programmability of Turing complete systems, while empowering, comes with specific vulnerabilities — this is especially true for public blockchains, where code is visible to anyone. The flexibility to craft any computation creates a broad array of possible outcomes, not all of which can be foreseen. Consequently, this leaves room for disruptions like software bugs and unintended functions that could hamper the protocol's effectiveness.

In centralized systems, unforeseen issues can be quickly rectified by the entity controlling the code through prompt updates. However, the decentralized architecture of blockchain complicates this process. Any modification to the code must undergo a community-driven voting process, delaying the implementation of critical patches.

As an example, consider The DAO, a decentralized venture capital fund set up on Ethereum in 2016. While often termed a 'hack,' the incident was more an exploitation of a previously overlooked vulnerability in the contract's code. This exploit allowed a malevolent actor to siphon over $150 million from an Ethereum smart contract, necessitating the rewind of the Ethereum blockchain to recover the stolen assets. This incident eventually gave way to the Ethereum Classic fork.

This incident was essentially a reentrancy attack, where the attacker exploited a flaw in the smart contract's code to withdraw funds illegally. Since The DAO debacle, the Ethereum community has made strides in improving coding best practices to avert similar vulnerabilities. However, the fluid nature of Turing complete systems—where new code is being constantly created—ensures that the threat of emerging vulnerabilities remains a persistent concern.

DeFiChain’s MetaChain Layer Combines the Best of Both Worlds

The upcoming integration of the MetaChain Layer is a pivotal milestone for DeFiChain, positioning it as the first blockchain to combine the Bitcoin and Ethereum ecosystems. 

Deliberately detached from the conventional UTXO (Unspent Transaction Output) system, the MetaChain Layer allows users the flexibility to either engage with the Turing complete partition, akin to Ethereum, or remain in the well-known UTXO realm of Bitcoin.

The choice is entirely up to you, and armed with the insights on the advantages and disadvantages of Turing completeness that you've gleaned from this blog post, you'll be well-equipped to make an informed decision.

For a deeper dive into DeFiChain's groundbreaking MetaChain Layer, don't miss these insightful blog posts:


Decentralized finance enabled on Bitcoin. A blockchain dedicated to fast, intelligent and transparent financial services, accessible by everyone.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.