Turing Completeness in Blockchain Explained

Comparison between Bitcoin and Ethereum

Miyoko Shimura

Published in

Coinmonks

4 min readJan 23, 2024

The concept of Turing completeness is often discussed when analyzing the capabilities of blockchain platforms.

What does it actually mean for a system to be Turing complete? What are advanteges and downsides when a blockchain is Turing complete?

This article breaks down Turing completeness using simple terms and real-life examples.

Origins of Turing Completeness

The concept is named after the British mathematician Alan Turing. In 1936, Turing published a paper titled “On Computable Numbers” that essentially laid the foundations of computer science.

In his paper, Turing described a hypothetical universal machine that could compute any computable sequence. This universal machine was the blueprint for what we now know as the general purpose computer.

Turing also established the limits of what algorithms a computer can run. Any system capable of replicating the universal machine is considered Turing complete.

Alan Turing in 1936, when he was 24 years old (Wikipedia)

What Does Turing Complete Mean?

The concept of Turing completeness is derived from the theoretical Turing machine. A system is considerd Turing complete if it can perform these key tasks.

Sequence — Execute a series of computational steps in the order they are provided.
Conditionals — Execute different computational paths conditionally based on certain criteria.
Iteration — Repeat computational sub-processes over and over.
Store Data — Store intermediate results for later use in memory.

The Turing machine was originally conceived as a theoretical, abstract model of computation by Alan Turing in 1936. However, physical constructions of Turing machines have also been built to help understand the concept.

The first successful construction of a physical Turing machine is credited to Charles Wynn-Williams in 1953 at the University of Cambridge.

A physical Turing machine model (Wikipedia)

Any system that meets the above criteria can theoretically perform the same computations as a general purpose computer. It may take longer and require more memory, but the final result will be the same.

What Does Turing Complete Mean? By Author

Turing Completeness in the Real World

A non-Turing-complete system is limited to performing particular tasks based on pre-defined instructions.

For instance, a traffic light controller is a good example of the non-Turing complete system. It has a fixed pre-programmed sequence of light changes and lack the capability to perform conditional logic or calculations beyond their simple sequence.

Another non-Turing complete system is a microwave oven. Microwave ovens are designed to heat food items for a set duration entered by the user, however, they do not possess conditionals, loops, or any way to run flexible programs.

In terms of gaming, Minecraft is Turing complete. While a definitive answer is elusive, Minecraft allows players to build intricate circuits and computers with its Redstone circuit system. It shows computational universality within game environments.

Why Does It Matter in Blockchain?

Turing completeness is an important concept in blockchain technology because it determines the computational flexibility and capabilities of the underlying blockchain platform.

It’s also important to note that Turing completeness introduces potential challenges, such as the risk of infinite loops or excessive resource consumption, which can lead to security vulnerabilities or network congestion.

Comparing Turing Completeness Between Bitcoin and Ethereum

Bitcoin and Ethereum are known as the most well-known example highlighting the difference in Turing completeness.

Bitcoin

Bitcoin purposefully avoids Turing completeness in its Script language. The capabilities are limited to focus on simple transactions.

Advantage — Limiting a blockchain to be non-Turing complete improves security and scalability by restricting what can be done on-chain. This also prevents any Bitcoin script from using excessive computing power and causing harm to nodes on the network.

Downside — It reduces flexibility for developers. Bitcoin’s primary focus remains on financial transactions, so developers cannot deploy complex smart contracts or dApps.

Ethereum

Ethereum was the first blockchain to support smart contracts and decentralized applications (dApps) with Turing completeness. It enhanced capabilities of blockchain technology overall.

Advantage — Ethereum allows developers to write code using the Turing complete Solidity programming language, and execute it using the Ethereum Virtual Machine (EVM), providing developers and users with increased flexibility.

Downside — Bugs and security risks are harder to control compared to non-Turing-Complete systems. Ethereum has to find a balance between computational power and safety of its blockchain ecosystem.

Some blockchain platforms, like Bitcoin, opt for a more restricted computational model to prioritize security and simplicity over expressiveness.

Author

Miyoko Shimura has over 8 years of engineering experience in the technology industry bringing together analytical perspectives.

DLT/Blockchain Mentor at German think-tank Frankfurt School Blockchain Center and Technical Editor at Coinmonks. For further updates please follow me on LinkedIn or Twitter 🌏

Portfolio https://linktr.ee/miyokoshimura