What is Turing Completeness?

In simple terms, a machine, system, or programming language can be considered Turing complete when it has enough runtime and memory to solve any computational problem. It means that the entity can manipulate data in various ways and is only limited by factors like available memory and energy.

When you write a line of code, you are essentially giving instructions to a machine on how to handle a specific set of input data. An example of this is an “if this then that” (IFTTT) statement. For instance, you could instruct a machine to analyze an article and output a ‘1’ if the text contains more than 500 characters. The machine would count each character, remember the count, and compare it to the input variable (500) after finishing the count. This process requires time and memory.

Instructions can be combined to create more complex instructions. For instance, you could instruct the machine to output a ‘1’ if the article contains 500 characters AND the letter “a” appears more than 20 times. As you can imagine, this process would consume more time and memory since the machine has to track two tallies while processing the input data.

In a Turing complete machine, all possible and logical instructions can be executed given sufficient time and memory. However, impossible steps, like dividing by zero, cannot be executed.

Why is Turing Completeness Relevant for Blockchain & Fintech?

One of the remarkable aspects of blockchain technology is its ability to facilitate smart contracts. These contracts involve agreements between parties that can be programmed into the blockchain to execute automatically. To understand this, let’s consider the XRP Ledger and apply our understanding of IFTTT statements.

Suppose you make an agreement with a friend that you will transfer 2000 XRP to them in the year 2023. The XRPL enables you to create an escrow wallet and instruct it to transfer the XRP to your friend’s wallet only if the year is 2023 (IF THIS: the year is 2023 THEN THAT: transfer to wallet). Smart contracts allow you to delegate the execution of agreements to a machine instead of relying on written agreements.

However, the escrow function of the XRPL is not Turing complete, meaning it has limitations on the conditions it can consider. In a Turing complete system, you could give infinitely complex instructions to be executed as long as they are logical. The only constraint would be the system’s memory, energy, and runtime, not the complexity of the instruction itself.

How Important is Turing Completeness?

Turing completeness provides developers and projects with a high level of freedom to create specific smart contracts for their projects. However, whether Turing completeness is essential is a topic of debate. One challenge with Turing completeness is that developers can overload a system by providing it with too many complex instructions.

In computing, a set of instructions can cause a machine to get stuck in an endless loop or execute an instruction that takes an impractically long time to complete. For example, if an agreement states that assets will only be released when the machine has solved for pi, the machine will run indefinitely, and the assets will remain locked. To mitigate this, smart contract capabilities developed for the XRPL, such as hooks, intentionally avoid Turing completeness. Additionally, as mentioned in this article, no machine has unlimited memory or runtime, meaning every system is practically limited in what it can execute.