Bitcoin and the claim of Total Turingness.

Craig Wright is a very controversial man — Bitcoin SV, Claims of being Satoshi Nakamoto, major plagiarism accusations- Overall, not the face of Blockchain you'd want. 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, or at least that's what the BSV community and Wright himself want you to believe.

We give Dr. Wright the benefit of doubt today. In 2014, Dr. Wright came out with a paper titled “Bitcoin: A total Turing machine” [1] and today we talk will about it.

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 all 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 posits the connection between Arithmetical Hierarchy and Turing degrees [2]. It is often stated defending the lack of need of Turing Completeness, and safety of decidability as another.

Wright proposes Bitcoin has been what he proposes to call a “Probabilistic Total Turing machine”. Let me try to summarize Craig’s claims

• 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.
• Wright states that Bitcoin is Turing Complete and proves so using the Ackermann functions.

Wright proposes that Bitcoin Script is a Probabilistic Total Turing Machine, which is something he proposes earlier. PTTM is different from PTMs. The alternate stack in the Script makes it Turing Complete.
Lack of looping in Bitcoin Script does not it non-Turing Incomplete. Since Bitcoin is formed using Primitive Recursion Functions, the script construct is Turing Complete.

Let’s try to dissect all this. Bitcoin does not support loops: This by itself does not make the script Turing Complete or Incomplete, but this does mean that the script lacks 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 [3] 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.

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, Bitcoin lacks For loops.
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 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 a futile discussion. 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 is 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!

Further Reading
[1] https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3265146
[2] https://youtu.be/TGE6jrVmt_I
[3] https://en.wikipedia.org/wiki/Busy_beaver