> disagree with your stated claim on (6) which is that there is no accepting state for (M) after an arbitrary move in (5).
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."?
> You're conflating (intentionally?) Bitcoin the system vs Bitcoin Script
What is "Bitcoin the system"? What are the parts of this system? You are saying this in a way that implies the existence of widespread and commonly accepted definition of the "Bitcoin the system". What is the name that definition gives to the part of the system that houses assorted external pieces of code that are required to stitch together different transactions in this article? Is it "Bitcoin application server", or "Bitcoin workflow engine", or "Bitcoin process management engine" or something of the sort? Are there guides on programming it? There must be some articles, possibly on wikipedia, that clearly show this component and give it a name. Would it be installed if I were to download the node software (for the Bitcoin or Bitcoin SV - does not matter).
I do not believe that "Bitcoin" implies that "arbitrary code that sends Bitcoin transactions to the network/mempool" is always part of Bitcoin.
> including the article which clearly says "Each step in running the Turing machine is triggered by a Bitcoin transaction."
Let's examine this.
The article opens with:
"We have empirically demonstrated that any Turing machine can be simulated on Bitcoin and thus definitively proven it is Turing-complete¹. We have implemented a Turing machine that recognizes balanced parentheses and deployed it on the Bitcoin blockchain."
And ends with: "Thus, any Turing machine can be simulated on Bitcoin, conclusively proving Bitcoin is Turing-Complete by definition. QED."
The part that you have cited is followed by the statement that you chose to omit. Let me pull a longer citation: "Each step in running the Turing machine is triggered by a Bitcoin transaction. The Turing machines can keep running, unless it enters an accepted state.<end of section>"
I am missing the place where the author has _clearly_ indicated that "The Turing machines can keep running, unless it enters an accepted state" is only possible with the aid of some external mechanism.
Abstract and conclusion are also entierly fail to mention the need for the Turing-complete external component that you have to have to keep the whole thing running.
I'd say that article "clearly says" something that is different entirely from what you claim it says.
> forgive me if your account age combined with Greg's precense, your arguments style, and the very peculiar coincidence that your handle matches a known BSV proponent on Reddit who Greg just happened to tag in connection with this post suggest you are being disingenuous.
FFS, you seem to be very fixated on attacking my personality instead of addressing my arguments, you know? No, I will not forgive you. If you won't stop, I will not respond to you anymore.
I can not agree with the claim that Bitcoin's Script Interpreter is 2PDA as it is defined in Hopcroft et al.
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.
Sorry, but the (max) board size is not known in advance. Board grows as the Turing machine simulator is running.
> 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.
I have nothing to do with nullc. I'd rather avoid personal attacks if it is OK with you.
> it can represent a single iteration of a larger program which is the point not being acknowledged.
I am actually acknowledging that bitcoin script can (only) represent a single iteration of a larger program. I acknowledge this and claim that this makes it not Turing complete, contrary to the claim in the article.
> 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.
It seems to me that we actually agree on the main points.
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
I am very familiar with Bitcoin script, and it was rather easy to confirm that BSV is using the same set of opcodes, and sCrypt compiles to bitcoin script, with obvious conclusions. So I think that I actually understand the topic (and the article) very well, thank you very much.
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?
Well, in Etherium, provided that sufficient amount of gas is paid for, I could have a contract that implements several (many?) iterations of the Turing machine - or any other computation.
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".
If you go over older posts on that medium blog, it seems to be a pattern with that particular author. He also has Conway's Game of Life implementation for 7x7 board, Rule 110 implementation for the tape of 5 elements, "machine learning" article with matrices that are 5x5 -- all because his language has to unroll loops (as Bitcoin script cannot loop), and loops with more iterations are therefore either unfeasible or straigh up impossible in sCrypt.
Despite that, he seems to be insistent that "Bitcoin is turing complete". Most curious.
Interesting to note that since sCrypt's "loop" construct simply unrolls the loop the constant number of times, proposed implementation will grow in size proportionally to the number of state transition rules (8 in the example in the article).
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.
So it looks like a better title would have been "saving the state of the turing machine on the bitcoin blockchain", as the claim of Turing completeness[1] seems disingenious - bitcoin script itself has no looping constructs and is decidedly non turing complete. The user has to call the contract as many times as necessary to ensure that Turning machine transitions between states, and the same user checks that the computation terminated.
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."
But you can just post it in the comment here, I will see it