Turing completeness is a concept in computer science that refers to a system or language's ability to simulate a Turing machine, a mathematical model capable of solving any problem that can be described with step-by-step instructions.
For a system or language to be Turing complete, it needs to have three primary abilities:
- It should be able to handle and manipulate data, such as numbers, words, or lists.
- It should provide instructions or commands for decision-making (like if-else statements) and repetition (like loops).
- It should offer a way to store and retrieve data from memory.
These capabilities enable a system or language to perform complex computations and solve various problems. Being Turing complete means having the tools necessary to tackle multiple tasks as long as the instructions are provided.
Turing completeness highlights the impressive potential of computational systems and languages to emulate the capabilities of a Turing machine.
Here are a few examples of systems or languages that are Turing complete:
-
Python: Python is a popular high-level programming language that is Turing Complete. It provides a rich set of data types, control structures (like if-else statements and loops), and features for memory management, allowing for complex computations and problem-solving.
-
Ethereum's Solidity: Solidity is a programming language designed to develop smart contracts on the Ethereum blockchain. It is Turing complete and includes data manipulation, control flow, and storage features, facilitating the creation of decentralized applications (DApps) with complex functionality.
-
Java: Java is another widely used programming language that is Turing Complete. It offers extensive libraries for data manipulation, control flow structures, and memory management, enabling the development of diverse applications.
Why is Bitcoin not considered Turing Complete?
Bitcoin is not considered Turing complete because its scripting language, Bitcoin Script, is intentionally designed to be limited in functionality. The primary purpose of Bitcoin Script is to define spending conditions and verify the validity of transactions within the Bitcoin network rather than supporting general-purpose computation.
Bitcoin's scripting language has a deliberately restricted set of opcodes (operations) that define the possible actions that can be performed. These opcodes are designed to ensure security and prevent potential vulnerabilities or unintended consequences that could arise from more complex scripting capabilities.
Here are a few examples of opcodes used in Bitcoin Script:
OP_ADD: This opcode adds the top two values on the stack and pushes the result onto the stack.OP_CHECKSIG: This opcode checks the validity of a digital signature against a provided public key. It verifies that the owner of the corresponding private key creates the signature.OP_EQUAL: This opcode compares the top two values on the stack and pushes a boolean result (true or false) onto the stack based on their equality.OP_HASH160: This opcode takes the top item on the stack, calculates its RIPEMD-160 hash, and pushes the result onto the stack. It is often used for address generation and verification.OP_VERIFY: This opcode checks the top value on the stack. It is removed from the stack if it evaluates to true (non-zero). An error is generated if it evaluates to false (zero) and script execution halts.OP_RETURN: This opcode is used to mark a transaction output as unspendable and can be used to embed arbitrary data on the blockchain.
Bitcoin Script lacks essential features necessary for Turing completeness, such as loops and arbitrary branching. It does not provide the ability to perform repetitive computations or make conditional decisions based on random conditions. This limitation is intentionally imposed to maintain the security and stability of the Bitcoin network.
Bitcoin aims to ensure deterministic and predictable transaction processing by limiting the scripting capabilities. It prevents potential issues like infinite loops, excessive resource usage, and unbounded computation that could harm the network's efficiency and reliability.
While Bitcoin's scripting language is not Turing complete, it still allows for implementing basic conditions and logic for transaction verification. However, it does not support complex computations and programmability in Turing complete languages like Ethereum's Solidity.
The intentional restriction of Bitcoin Script is a trade-off made to prioritize security and maintain the integrity of the Bitcoin network as a decentralized digital currency system rather than a general-purpose computing platform.
Turing completeness is very dangerous, particularly in open-access systems like public blockchain, because of the halting problem.
What is the halting problem?
The halting problem is a famous problem in computer science that determines whether a program will eventually halt or run indefinitely. In simpler terms, it asks whether it is possible to create a program or an algorithm that can predict whether another program will eventually stop or run forever.
The mathematician and logician Alan Turing first formulated the halting problem in the 1930s as part of his work on computability theory. Turing showed that no general algorithm can solve the halting problem for all possible programs.
Let's consider a simple example to illustrate the halting problem.
def f(n):
if n == 0:
return 1
else:
return f(n-1) + f(n-1)
This program defines a recursive function f(n) that takes a non-negative integer n as an input and returns 2^n as an output. However, if we give a negative integer as an input, the program will never stop because it will keep calling itself with smaller and smaller negative values. So, the halting problem asks whether we can write another program that can look at this program and tell us whether it will halt or not for any input.
The answer is no, we cannot. Alan Turing proved in 1936 that the halting problem is undecidable; that is, no general algorithm can solve it for all possible programs and inputs. He used proof by contradiction: he assumed that such an algorithm exists and then showed that it leads to a logical contradiction. Let's look at the following code to understand it better. Please read the comments in the code; they will help you understand the flow.
# This is the supposed algorithm that can solve the halting problem
# It takes two inputs: a program P and an input I
# It returns either "halt" or "loop" depending on whether P halts or loops on I
def H(P, I):
# Some magic code that can do this (but actually doesn't exist)
pass
# This is the new program that takes another program Q as an input
# It runs H on Q and Q (that is, it gives Q itself as an input to H)
# Then, it does the opposite of what H says: if H says "halt", B loops; if H says "loop", B halts
def B(Q):
# Run H on Q and Q
result = H(Q, Q)
# Do the opposite of what H says
if result == "halt":
# Loop forever
while True:
pass
elif result == "loop":
# Halt
return
# Now, let's see what happens if we give B itself as an input to B
# That is, we run B on B
B(B)
The code shows how the paradox arises when we run B on B. There are two possible outcomes:
- H says that B halts on B. In that case, B will loop on B because it contradicts what H says. But this contradicts what H said because H said B halts on B.
- H says that B loops on B. In that case, B will halt on B because it contradicts what H says. But this also contradicts H's statement because H said B loops on B. In either case, we get a contradiction between what H says and what B does.
This means that H cannot be correct for all possible inputs and, therefore, cannot exist as a general algorithm for the halting problem.
I know this is a bit complex to get, but what I can do is provide you with a video reference:
Turing and the Halting Problem by Computerphile
https://www.youtube.com/watch?v=macM_MtS_w4&embedable=true
Modern printers are Turing complete and can be given files to print that send them into a frozen state. The fact that Ethereum is Turing complete means that Ethereum can compute any program of any complexity. But the flexibility brings some thorny security and resource management problems. An unresponsive printer can be turned off and turned back on again. That is not possible with a public blockchain.
Satoshi Nakamoto, the pseudonymous creator of Bitcoin, designed Bitcoin Script to be Turing incomplete for a reason. He wanted to prioritize the security and simplicity of the network over its functionality and flexibility. His mission was to create a truly decentralized digital currency system rather than a general-purpose computing platform.
However, some have argued that Bitcoin Script is not truly Turing incomplete, as it can be extended or modified to achieve Its completeness. For example, some have proposed using oracles (external sources of information) or covenants (restrictions on how coins can be spent) to enable loops or recursion in Bitcoin Script. Others have suggested using sidechains (parallel blockchains) or layer two solutions (off-chain protocols) to run Turing complete smart contracts or DApps on top of Bitcoin.
I hope this article gave you a better understanding of why Bitcoin was made the way it is.
I thank you for taking the time to read my article.
Also published here.