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
Top comments (5)
Great discussion. My colleague, Dr. Clemens Ley, founder of bitcoincomputer.io has discovered how to make Bitcoin SV turing complete. I would love to have you sit in on a discussion with us sometime. -Greg
I'd love to join sometime later this week!
Fantastic, we meet 2x a week, on Mon & Thurs. You can join for a little while this Thurs if you are interested. Otherwise, we can setup another time. Feel free to join our telegram group & ask any questions you may have as well. We have lots of people who are willing to help. t.me/joinchat/KH6MAUWRuUl8RZdVkeMMAw
-Greg
This misses the whole point. "Bitcoin" is said turing complete because you can create an UTXO that will execute a certain script code over and over, bot because script is TC (of course script isn't TC), but the whole UTXO can only execute a predefined script code over and over hence the turing completeness (each tx will be a step of the turing machine for instance)
However it might be true that the 200 opcode limit makes it non TC, but if you remove this artificial limit it's 100% TC. I think 100opcode is enough to loop anyway, so maybe with 200opcodes you are TC
(And eth is not quasi TC wtf it's just TC, and yes if you don't support loop it means that you are not TC, and no the bitcoin network is not more "turing" than something else it makes 0 sense)
To loop => xiaohuiliu.medium.com/op-push-tx-3...
Neither Bitcoin nor Bitcoin’s Script is Turing-complete. Bitcoin is essentially a finite automaton.
ijcttjournal.org/archives/ijctt-v6...