Bitcoin and the claim of Total Turingness.

A lesson in designing Blockchain languages.

Craig Wright is a very controversial man — Bitcoin SV, Satoshi Nakamoto claims, major plagiarism accusations— in fact, if you mention him on Reddit, you will be downvoted to oblivion. But Craig Wright is also a very smart man, much more than the Twitter handles in the Crypto Community would have you believe. His degrees and years of experience are something you cannot ignore — Oh wait, except, you can. However, we give Dr. Wright a benefit of doubt today. In 2014, Dr. Wright came out with a paper titled “Bitcoin: A total Turing machine” and today we talk all about it.

Note: This post does not have a conclusion, I am not very good at Turing Computers as of 02–05–2020, thus will not claim to be. I have used the terms “Claims”, “States”, “Proposes” not because I doubt the intellectual honesty of the authors and review panel, but because I do not have a 100% understanding of such systems.

Photo by Mauro Sbicego on Unsplash

If you don’t know about Turing Machines, now is a good time to talk about it. Turing machines are theoretical models of computation that represent an abstract machine. Turing machines are tapes divided into cells.

A Universal Turing Machine

Turing machine was put forth by the legendary Alan Turing in ’36 and it proved something very important: the uncomputability of the Entscheidungsproblem. Turing Machines cannot be implemented in real life of course, because we don’t have infinite tapes in real life, and because these machines aren’t optimized for real-life implementations. For example. Real Life computers use RAMs, which TMs don’t. But TMs can compute anything a real computer can, given duration of computation is not an issue.

Turing Completeness is the idea that any program that is Turing Complete will halt. And any program that halts will not tend to infinity. From here we deduce that a Turing Machine should run infinite time.

How does this relate to Bitcoin?

Bitcoin’s Script is a stack-based, non-Turing Complete programming language. And there is a lot of conversation about this, especially attacking the Ethereum community for being Turing complete, and the lack of need to be Turing complete because “Post’s theorem”.

Representation of a Stack Data Structure

Post’s theorem is often stated defending the lack of need of Turing Completeness, and safety of decidability as another. But then Wright comes in and says Bitcoin has been what he proposes to call a “Probabilistic Total Turing machine”.

Let me try to summarize Craig’s claims—

1. Wright proposes that Bitcoin is equivalent to the machine proposed in Wolfram’s conjecture, which states that a 2 state, 3 symbol Turing Machine is a Universal Turing Machine. By this, a proposition establishes that Bitcoin Script must also be a Universal Turing Script.
2. Wright states that Bitcoin is Turing Complete and proves so using the Ackermann functions.
3. Wright proposes that Bitcoin Script is a Probabilistic Total Turing Machine, which is something he proposes earlier. PTTM is different from PTMs.
4. The alternate stack in the Script makes it Turing Complete.
5. Lack of looping in Bitcoin Script does not it non-Turing Incomplete.
6. Since Bitcoin is formed using Primitive Recursion Functions, the script construct is Turing Complete.

Let’s try to dissect all this.

1. Bitcoin does not support loops: This by itself does not make the script Turing Complete or Incomplete, this makes the script lack Control Structures. Sure, if-else is there, but without For loops, there is a lack of Control. This is not a bug in the language, it is a feature. A small script such as Busy Beaver will cause the Bitcoin network to return DoS overtime at worst, and slow down the hash rate at best. This was implemented to increase decidability and safety.
2. Two stacks don’t make a Turing Complete Machine: To Simulate a Two-Stack PDA (Which is Turing complete), you need a control structure. As I said in [1], Bitcoin lacks For loops.
3. Bitcoin limits the number of non-Push operations you can do per script: If you look at Bitcoin’s Github, you will see the following piece of code: static const int MAX_OPS_PER_SCRIPT = 201; This means that you can do 201 non-Push ops per script. This is again to safeguard against undecidable problems. So even if you implemented a 2PDA, you would be practically limited by this.

Whether or not Bitcoin is Turing Complete is, to me, a futile argument. Bitcoin Network is “more” Turing than other networks because of its size (That statement holds no scientific value, I said it as a figure of speech). Bitcoin Script it better off Turing incomplete by design, even though there might be some “proof” of it being otherwise. P2P consensus networks need to implement some form of decidability in their scripts. Ethereum, for example, has a Gas-system. It’s quasi-Turing Complete for that reason. Bitcoin Script, if used outside of the Bitcoin network, would have issues because it is Turing Incomplete by design, but a few modifications, and you can build it to be Turing Complete. But in practicality, no system is truly Turing Complete. I would love your comments about this!

🌺 Hey, hope you enjoyed reading that article. I am Abhinav, editor @ The Crypto Element. It takes a lot of work to research for and write such an article, and a clap or a follow 👏 from you means the entire world 🌍 to me. It takes less than 10 seconds for you, and it helps me with reach! You can also ask me any questions, or point out anything, or just drop a “Hey” 👇 down there. I 💓 making new friends!