What Is Turing Completeness?

In short: given enough run time and memory, a turing complete machine, system or programming language may be called turing complete when it can solve any computational problem. Theoretically, the entity in question should be able to execute any form of data manipulation and only be constrained by its memory, available energy, etc. 

When you write a line of code, you are basically giving a machine instructions on what to do with a set of input data. A simple IFTTT (if this then that) statement is a clear example of this. For example: you could tell a machine to analyze this article and tell it to output a ‘1’ if the text contains more than 500 characters. A machine would in that case count each character in the article, memorize the count and compare its final count number to your input variable (500) after completing the count. This process takes time (albeit very little in modern computing) and memory. 

Statements can be combined in order to make instructions more complex: you could tell the machine to output a 1 if this article contains 500 characters AND contains the letter “a” more than 20 times. You can see that this process would cost more time and memory as the machine now has to keep two tallies while processing the input data. 

In a turing complete machine, all conceivable and logical, instructions can be executed by the machine if the machine is given enough time and memory (logical meaning that a machine cannot be told to execute an impossible step e.g. output a 1 if the characters in this article equal 500/0, as dividing by zero is impossible).

Why Is Turing Completeness Relevant for Blockchain & Fintech? 

One of the great aspects of blockchain technology is that it can enable smart contract capability, meaning that a set of agreements between two parties can be given to the blockchain as a set of instructions so that it automatically executes them. Let’s apply what we have learned about IFTTT statements to the XRP Ledger to understand how this works. Let’s say you make an agreement with your friend that he will receive 2000 xrp from you when the year is 2023. The XRPL has a function that enables you to put 2000 xrp in an escrow wallet and give it the instruction to transfer the XRP to your friend’s wallet IF the year is 2023 (IF THIS: the year is 2023 THEN THAT: transfer to wallet). Whereas historically, you and your friend would have to write down and remember your agreement, smart contracts enable you to outsource the execution of the agreement to a machine.

The escrow function of the XRPL is, however, not turing complete. Meaning that the set of conditions the escrow can consider is limited. In a turing complete system, you could give an infinitely complex instruction to be executed, as long as it is logical. The only constraint the system (assuming a logical instructions) would have is its memory, energy and run time, but not the complexity of the instruction itself. 

How Important Is Turing Completeness?

Turing completeness gives developers and projects a high degree of freedom to develop specific smart contracts for their projects. However, whether turing completeness is essential, is open to debate. The problem with turing completeness is that developers and projects can overload a system by feeding it too many complex instructions. 

One problem in computing is that a set of instructions can cause a machine to be stuck executing a set of instructions indefinitely, either because the instruction creates a loop or simply because the instruction is so complex that its execution will take too long to be convenient for the parties entering the agreement (if we agree that you only get your assets when the machine has solved for pi, the machine will run forever and the assets will always remain locked). For this reason, smart contract capabilities developed for the XRPL, such as hooks, are deliberately not Turing-Complete, as Wietse Wind points out. Furthermore, as pointed out in this article, no machine has unlimited memory or run-time and, thus, in practice, every system will always be limited as to what can be executed.