Turing Complete

Turing Complete refers to a machine that, given enough time and memory along with the necessary instructions, can solve any computational problem, no matter how complex. The term is normally used to describe modern programming languages as most of them are Turing Complete (C++, Python, JavaScript, etc.).

What is a Turing Machine?

Before modern-day computers, Alan Turing hypothesized that there would one day be a machine that could solve any problem. This machine became known as the Turing Machine.

Alan imagined his machine as a long piece of tape with information written on it in the form of binary code (1s and 0s). The machine would also have a read/write head that moves along the tape reading each square, one by one. The code would ask the machine a computational problem, and the tape would be as long as was needed to achieve a solution.

As the head moves along the tape, the machine follows simple instructions that govern how it reacts. It reads the tape, follows the instructions, and perform a certain action to write a new code as it moves along. This new pattern of code is the answer to the problem. Turing’s hypothetical machine could answer any computational problem that could be expressed in code (and that had a calculable answer).

A device or programming language is considered to be Turing Complete when it can replicate a Turing Machine by running any program or solving any problem the Turing Machine could run or solve. On the other hand, if a device or programming language is not able to do it, then it is said to be Turing Incomplete.

A simple calculator is an example of a system which is Turing Incomplete since it can only do a few types of calculations. In contrast, a programmable scientific calculator (able to perform all kinds of calculations) can be deemed as a Turing Machine.

Blockchain and Turing Completeness

While some applications of blockchain technology are Turing Complete, others are Turing Incomplete. This varies according to the scripting technology implemented. For example, the scripting language used in Bitcoin is intentionally designed as Turing Incomplete because it serves its purpose and increased complexity would potentially introduce problems. By keeping it simple, the developers can predict with high accuracy how it is going to react in the finite number of situations in which it is used.

Ethereum, on the other hand, is built as a Turing Complete blockchain. This is important because it needs to understand the agreements which make up smart contracts. By being Turing Complete, Ethereum has the capability to understand and implement any future agreement, even those that have not been thought of yet. In other words, Ethereum’s Turing Completeness means that it is able to use its code base to perform virtually any task, as long as it has the correct instructions, enough time and processing power.