Glossary
Turing completeness
In computability theory, Turing completeness is the property of a language or system capable of executing any algorithm, no matter how complex, as long as it has access to unlimited resources and time. The name is in honor of the mathematician Alan Turing, one of the fathers of computers, who worked on the so-called problem of universal computation.
The type of programming we can do on top of Bitcoin has limitations; it is not Turing complete. Why not? Is it that Satoshi Nakamoto was that lazy? Far from it. This was deliberate to make the system more secure and predictable. The problem with Turing complete languages is that we cannot predict their outcome, which can be dangerous for blockchains.
How often have you had to close a program or even restart your computer because it crashed? Making a program crash, or going into an infinite loop, is one of the simplest things a programmer can do. Sometimes this happens intentionally, but most of the time, it doesn’t.
When your computer crashes, the worst that can happen is that you have to turn it off and on again. But it is not possible to do that with the blockchain. We cannot allow a program that runs on the blockchain to crash or enter an infinite loop. That is why the Bitcoin script is purposely incomplete: it is designed to disallow loops in the algorithm, thus avoiding infinite loops or even very long executions.
As scripts submitted to Bitcoin are written by its users, we need to prevent malicious executions from being submitted to the network. Alan Turing proved, in 1936, that it is impossible to predict a program’s result before it is executed. This is called the Halting problem. This means that, in Turing complete languages, it is impossible to predict how long a program will take to execute.
Bitcoin solves the Halting problem using purposefully incomplete language. Thus, malicious or careless users lack the necessary tools to crash the network. The execution becomes predictable through the usage of Bitcoin script. Years later, Ethereum solved the Halting problem another way, introducing the gas fee idea. This allows blockchains like Ethereum, Neo, Solana, and others to have Turing complete languages capable of running any program. This marks the birth of smart contracts on the blockchain.
