What is Turing Complete? | CryptoWallet.com

What is Turing Complete?

Turing Complete refers to the ability of a computer or system to run any algorithm or solve any computational problem, provided it is given the necessary instructions, time, and memory. Most modern programming languages are Turing Complete, such as C++, Python, and JavaScript.

In order to be referred to as Turing complete, such a system must be able to do what a Turing machine — a theoretical machine developed by mathematician Alan Turing — can do.

Turing Machine

During the early generations of computers, Alan Turing deduced that there would one day be a machine that could solve any problem. This machine became known as the Turing Machine.

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 duplicate  Allan’s Turing Machine by running any program or solving any problem that the Turing Machine could solve. However, 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. But a programmable scientific calculator which is able to perform all kinds of calculations can be considered as a Turing Machine.

Blockchain and Turing Completeness

Although some applications of blockchain technology are Turing Complete, others are Turing Incomplete. This is dependent on the scripting technology that a blockchain has. For instance, the scripting language used in Bitcoin is intentionally designed as Turing Incomplete because it serves a single purpose and making it more complex would potentially introduce problems. By keeping it simple, the developers can predict with high precision how it is going to react in the finite number of situations it is used.

In contrast, Ethereum is built as a Turing Complete blockchain. This is crucial because it needs to understand the agreements of various smart contracts. By being Turing Complete, Ethereum has the ability to understand and implement any future agreement, even those that have not been thought of yet. Ethereum is Turing Complete because its codebase can perform any task, as long as it has the correct instructions, enough time and processing power.

An important feature of a Turing-complete language is loops. This allows the programming language to do a set of instructions repeatedly.