Turing Complete Meaning

Jan 5, 2024 | Updated Jan 5, 2024

The term Turing Complete refers to a system that can perform complex computations by design when given sufficient resources, such as time and memory.

What is Turing Completeness?

Turing Completeness defines a system or computer’s potential capacity to solve any complex computation problem if provided with enough memory and time. Alan Turing first proposed the Turing machine, a mathematical computation device that can solve any problem, in 1936. There isn’t actually a physical device or machine per se, but rather, the machine is theoretical.

The hypothetical machine’s reaction relies on the instructions fed to it. If asked a computational problem, it reads the instructions and performs operations to write the answer in the code pattern. Basically, if a problem has a calculable answer and is expressible as a code, then a Turing machine can solve it.

Therefore, a system is said to be Turing complete if it can simulate a Turing machine.

Most modern programming languages, such as Solidity, Python, C++, and Java, are considered to be Turing complete. This implies that they can simulate a Turing machine, i.e., they can write a program or solve a problem that a Turing machine can write or solve. A programming language or machine that is unable to do so is considered Turing incomplete.

What Does Turing Complete Mean in Blockchain?

Generally, it is characterized by:

Logical loops: The ability of a system to perform a function or a set of instructions repeatedly.
Input/output operations: The machine can read and write data, i.e., take input and produce output based on the input data.
Computation: The system should be capable of computing any calculable problem that a Turing machine can tackle.
Conditional branching: Its behaviour can change based on the data value.

Blockchains meeting these criteria are regarded as Turing complete. In the blockchain context, it implies that the programming languages used to develop smart contracts can solve any computational problem. For example, Ethereum uses Solidity for its native code and smart contracts. This is essential for the blockchain to comprehend the terms of smart contracts and even enforce future agreements. Simply, Ethereum’s Turing completeness allows it to execute virtually any task if provided with the right instructions and enough resources, such as time and processing power.

By comparison, Bitcoin uses a scripting language, called Script, that is not Turing complete. This is because Script was specifically designed to handle basic functionalities, such as transferring values and writing some simple smart contracts. It is intentionally Turing incomplete to prevent loops from consuming excessive resources for nodes. In addition, Turing completeness could jeopardize the integrity of the Bitcoin network as it allows arbitrary code to be executed, opening the network up to additional attack vectors

It is noteworthy that blockchains are not required to be Turing complete.