Turing Machines on Bitcoin
xiaohuiliu.medium.com
xiaohuiliu.medium.com
1: The claim is "It is straightforward to adapt the Turing machine contract above to implement any other Turing machines, by simply changing the states, the symbols and transition function. Thus, any Turing machine can be simulated on Bitcoin, conclusively proving Bitcoin is Turing-Complete by definition. QED."
With the approach proposed in the article I need to have an external Turing-complete "controller" that would keep calling the contract.
At this point, what is the benefit I am getting from having this "contract" at all? I would be better off with a just serializing the state of my machine and putting it into OP_RETURN, getting a much smaller blob to store on the chain. So I will save on the fees, could implement my Turing machine (or anything else, really) in the language of my choice, not constrained by the absence of loops and function calls.
Article essentially uses bitcoin blockchain as a database (I hesitate to use the word "ledger"), and the use of "contract" is just a gimmick, seemingly introduced just to prop the absurd claim that bitcoin somehow becomes turing-complete when external turing-complete controller performs "contract calls".
> At this point, what is the benefit I am getting from having this "contract" at all? I would be better off with a just serializing the state of my machine and putting it into OP_RETURN, getting a much smaller blob to store on the chain. > Article essentially uses bitcoin blockchain as a database
This is just plain wrong and not at all what this article is about. In the article, a script is developed that enforces state transfer by the specified transition table, i.e. only a specific set of bitcoin transactions are allowed on the state, namely the ones from the transition table.
So what is the article about, then? I started this thread disagreeing with the claim that material presented in the article somehow makes bitcoin turing complete and claiming that it, in fact, is not. You seem to be arguing this point with me, but I am not exactly sure what your (counter)arguments are.
So a contract with 50 transition rules (or just carelessly bumped up constant N in the source code) would be much larger as it has to repeat its inner loop N times -- and there is nothing you can do about it, as functions and function calls are syntactic sugar as well, and function bodies are immediately inlined at the call site.
All that is moot in my opinion though. The issue was settled a long time ago before Bitcoin's founding.
“If a language L is accepted by a Turing Machine, then L is accepted by a two-stack machine” - Theorem (8.13) - Introduction to Automata Theory, Languages, and Computation - Hopcroft, Motwani & Ullman.
Bitcoin's Script Interpreter is an implementation of 2-PDA (two-stack pushdown automata).
What often happens in these debates is that folks conflate the Program, Language and Machine. Teasing these out to their discrete parts where Program is what sCrypt produces, Language is Bitcoin Script, and Machine is the Bitcoin Script Interpreter leads to more precise discussions.
My position is that as per the Minsky Theorem, Bitcoin's Script Interpreter is Turing Equivalent. Memory and resource-constraints aside.
Anyone who thinks that resource-constraints precludes a Machine from being "Turing Complete" should read papers like these: (Turing machines with restricted memory access) https://www.sciencedirect.com/science/article/pii/S001999586...
If you want to dig deeper, then you can solve Bitcoin's State Transition function yourself. Here's a good worked example, but it requires that you have knowledge of Automata Theory: https://www.chegg.com/homework-help/questions-and-answers/ma...
Definition of the 2PDA as given by Hopcroft relies on the notion of looping with the number of loop iterations not known or fixed in advance.
For example: p. 351 (2nd ed), proof of the theorem 8.13 that you referenced, items 5 and 6 state:
5. [Our two-stack machine S] simulates a move of [one-tape Turing machine] M as follows: ....
6. S accepts if the new state of M is accepting. Otherwise, S simulates another move of M in the same way.
Bitcoin script is only capable of doing the "Otherwise, S simulates another move of M in the same way." part a limited, predetermined number of times.
The book introduces the notion of language accepted by PDA and TM in exactly the same way. See, for example, sections 6.2.1 "Acceptance by final state" and 6.2.2 "Acceptance by Empty Stack" that formalize the notion of language accepted by the PDA. Both of them feature "many transition steps" notation, without specifying the upper bound on the number of steps.
If the upper bound is fixed, any language accepted by such PDA could be trivially extended to not be accepted by iteration-limited PDA, but still be accepted by the PDA without iteration limit.
So Bitcoin's Script Interpreter is NOT an implementation of 2-PDA, and Minsky's Theorem is not applicable.
E.g. In bitcoin script any encounter with OP_RETURN moves you immediately into an accepting state whereupon the program halts and interpreter performs a predicate evaluation on the state of the stack.
Hopcroft et. al. also makes no claim on the input to the FSM being infinite (requiring an infinite loop). Quite the opposite. The FSM clearly reads the Program until it encounters a "simulated blank" signifying the end of input, so it can start processing the "tape".
A simpler way of satisfying the requirement of Bitcoin Script Interpreter as a 2-PDA is simply to define the State Transition function in terms of Bitcoin Script Primitives.
Q × ( ∑ ∪ {ε} ) × S × Q × S*
Where:
* Q is the finite number of states
* ∑ is input alphabet
* S is stack symbols
* q0 is the initial state (q0 ∈ Q)
* I is the initial stack top symbol (I ∈ S)
* F is a set of accepting states (F ∈ Q)
Resolving each of the above is left as an exercise to the reader.
I do concede that the actual usefulness of the computation is limited to the extent that the Bitcoin Implementation limits the size of the "input tape" i.e. the limits on size of Script.
Hence the need for Big Blocks and unbounded Script sizes to allow the market to discover the correct trade-offs between economic benefit and computational cost.
No, this is not what I claim.
I claim that if after the step 5 the new state is not an accepting state, 2PDA has to perform another step 5 and keep doing that until an accepting state is reached, and bitcoin script cannot do "perform the step 5 until a condition is met" bit.
Could you please tell me how (in terms of opcode) the second part of the step 6 will look like, namely "Otherwise, S simulates another move of M in the same way."?
The claim you're making regarding "two stacks" is technobabble initially created by Wright which was clearly discredited many years ago, e.g.
https://www.reddit.com/r/btc/comments/6hjxiy/new_craig_wrigh...
In Bitcoin script the additional stack doesn't increase its computational power at all: Ignoring the operation count limits, any script using the altstack can be converted with the addition of some extra stack manipulation operations to one that doesn't use it at all.
Folks are now free to reference this link in future posts as a claim that @roconnor's post has been discredited.
See how that logic works ?
Roconnor is a published expert in this domain, in fact his PHD thesis ( https://r6.ca/thesis.pdf ) was on formalizing and machine proving Gödel's incompleteness theorem. Instead, without justification or argument, you would like us to take the word of a person who failed the only theory of computation class he's taken and has been found by multiple courts to be an unreliable witness, a liar, and a forger-- a person for who has collected astounding sums on money on the promise of someday sharing some storied treasure which he-- as he's recently been forced to admit in court-- has no access to.
I see how your logic works, and I expect that most readers of this thread will as well.
I suggest you stick to the tech (like I'm doing), and leave the personal drama at home, 'cause I'm not interested in hearing about whatever bun-fights you are engaged in with whoever it is you're referencing above.
If you have a technical position of your own, I'd be glad to hear it. So far I've only heard appeals to the authority of a poorly-written, zero-detail, no-technical analysis opinion of someone I've never heard of until you started leaning on their opinions for claims in support of your position.
I've already pointed this out, so rather than repeat it I thought I would link to an expert who was speaking about exactly your claim (which is just Wright's claim), making the same argument I made.
Both implementations have a large intersection. Dogecoin, Litecoin and Dash also use the bitcoin protocol and should also work.
> Sure, it can be added to BTC
The presented solution does not require a protocol change. BSV is essentially the original bitcoin protocol (with few small exception); nothing was added to the protocol to implement the turing machine. BTC has some of the scripting opcodes disabled but they can either be implemented using other opcodes (no change) or they could be reenabled as a new SegWit deployment (requires change). However, the issue you'll run into in practice is that the reference implementation (Bitcoin Core) has very small limits set and discourages scripting. You'll have to find a miner that mines the custom scripting transactions. And, well, fees are another issue.
Can you list what those default limits are, and how big the needed changes are?
I'm getting the idea that it's either 1. A fun proof of principle project 2. entertains more "compute" ideas on blockchains, kinda like Ethereum
Wright isn't particularly technically sophisticated and early on he made the error of claiming Bitcoin Script was turing complete on the basis of it having "multiple stacks". It transparently is not-- for it can only execute a number of operations fixed in advance, and lacks any looping, recursion, or similar and any script using the altstack can be turned into a slightly larger one that doesn't. Rather than retracting or recontextualizing the false claim, he's since just continued to double down on it, presumably because doing so helps further isolate the victims of his fraud from people who are technically competent.
To support these repeated false claims, Wright eventually published “A Proof of Turing Completeness in Bitcoin Script”, which turned out to be almost entirely plagiarized from a 1964 paper by Corrado Böhm, the discovery of which apparently result in Wright being kicked out of CNAM. https://samwill102244.medium.com/anatomy-of-a-fraud-a-deep-d...
Publications like the one here are intended to confuse the reader about the definition of turing completeness, and are instead just pointing out the same points that were made that turing completeness was unnecessary in the context of Bitcoin ( https://www.youtube.com/watch?v=TGE6jrVmt_I / https://cyber.stanford.edu/sites/default/files/russelloconno... )which had been pointed out by the community back even before Wright ever knew of Bitcoin.
The whole matter is doubly absurd because it would be completely trivial to make Bitcoin script actually turing complete and could be done without breaking compatibility with the existing network. But it is generally considered expressly undesirable to do so by technical experts, because it would remove the existing guarantee that the runtime of all scripts can be determined and limited statically and because it wouldn't actually increase the utility of the system.
Recent court documents have exposed that Wright's activities are being funded by an advanced fee fraud scheme where he promises wealthy investors large amounts of "satoshi's bitcoins" in exchange for loans. Based on their own reports it appears the the total amounts taken are in the hundreds of millions of dollars now, or even more. This would all mostly just be sad and amusing except for Wright's propensity to file lawsuits against people who point out his fraud (such as myself-- he's sued me demanding 6 billion dollars in damages!)
For more information on the BSV scam and Wright's fraudulent claims checkout https://www.reddit.com/r/bsvscam/ and https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-m...
While most of what you write is true (and I believe that the article was written in bad faith), as the article uses state changes in the Turing machine as Bitcoin transactions, it is trivial to statically check the runtime of a state change itself. Whether it's a useful addition to Bitcoin or not is another question though.
Unrolling once is still what I'm referring to there.
> a new technique that was only recently developed.
That's simply false. E.g. search for 'covenant' or 'recursive covenant'. It's also described on the mailing list as far back as 2011.
(And, incidentally, the first example of a turing complete machine controlling the release of a transaction on Bitcoin was in 2016 and was vastly more efficient and private than the the approach used by the post-- https://bitcoincore.org/en/2016/02/26/zero-knowledge-conting... )
Whatever I read regarding "covenant" requires a protocol change. Independent of who described the underlying technique first, this doesn't invalidate the proof.
Sure it is. The state machine expressed in the script checks one (or more) steps of the update rule. That's what we mean by unrolling, not the "or more" part but the fact that the script is just running a simple circuit for a fixed operation.
> doesn't invalidate the proof
Proof of what? It's not a proof of script being turing complete. If you're claiming that it's that-- it's invalid on its face.
If you're saying it's a proof that script can implement a static state machine that runs one or more steps at a time checking some transcript computed by an external process and check consistency of state using the outputs-- then sure, that's not news, nor controversial, it's been known almost all of the system's life.
Despite that, he seems to be insistent that "Bitcoin is turing complete". Most curious.
What am I up to? My beef with the article is quite simple: the article is clearly written with a singular goal in mind, to claim that "Bitcoin is turing complete", with is trivially verifiable falsehood, so I failed to resist "someone is wrong on the internet" impulse. Are you implying that I am arguing in the bad faith?
There seem to be many other article by the same author making the same claim, with equally tenuous "proofs": https://xiaohuiliu.medium.com/play-conways-game-of-life-on-b... and https://xiaohuiliu.medium.com/turing-complete-rule-110-on-bi...
So the question should rather be "what is he up to?". Probably just a promotion for his language or clickbait titles.
To explain the Game of Life contract you're linking to: The `loop`, again, is just an implementation detail to go over each field on the board in a *single* transaction. It's not part of any proof. The actual turing-complete element - letting the GoL run - happens outside: Each generation state transfer happens via a bitcoin transaction.
I do agree with you that single contract transaction is not turing-complete. I also agree that turing-complete element happens outside.
My disagreement is with the following:
1. I disagree that "loop is just an implementation detail and is not part of any proof". In the GoL article there is a claim that (a)Game of Life board could simulate a turing machine and (b)article provides implementation of GoL board in sCrypt, therefore "Bitcoin in turing-complete". However, the board in article is limited (due to loop inlining) and cannot be made 1000s x 1000s (as required for the simulation of the turing machine) precisely because of the loop unrolling. I also note that author does not point out this limitation (in any of his articles, it seems) - the claims are always "we can simulate Game of Life, we can do Machine Learning, we can simulate Rule 110 automata" without any mention that these are toy examples that hardly do anything and can't scale even by an order of magnitude. So loop is indeed an implementation detail, but quite essential one, it seems.
2. More broadly, I am agruing against the claim that "Bitcoin is turing complete" made in this and other articles by the same author. But, again, it seems that on this point we are actually in agreement
In the GoL example, one generation update is performed in every transaction. Since the board size is known in advance, it totally makes sense to unroll the loop. If you want to do boards larger than that, like the 1000x1000 you mention, you run into script limits. What you can then do instead is, for example, to update the first half of the board in one transaction and then the second half in another transaction, i.e. two transactions are one generation.
Bitcoin is turing complete as shown in this article.
> What you can then do instead is, for example, to update the first half of the board in one transaction and then the second half in another transaction, i.e. two transactions are one generation
Yes, we just need to add the external "driver" that partitions the board, determines the bounds of board parts, constructs transactions that do all the necessary work of updating the board, checks whether the computation is finished - in other words, does the hard work of partitioning the computation in the chunks of fixed predetermined size, which is only necessary because bitcoin script is not turing-complete.
This is not what the article claims to show. It shows that the system bitcoin is turing complete.
Added to this, having an "external driver" and the system being turing-complete are not mutually exclusive.
In many cases, they are. For instance, if you tack on an already-Turing-complete component to the existing "system", then it's disingenuous to call the existing system Turing complete.
Further, this "covenant"-style system isn't really what Turing had in mind when he spoke of an "automatic machine".
Further further, this has nothing to do with Craig Wright, who famously called Script itself Turing complete in a plagiarized paper, and said that the "alt stack" is critical for it to be Turing complete.
Nonsense.
But you can just post it in the comment here, I will see it