8 ms·

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

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."

shilch 5y ago
The presented solution does *not* loop inside bitcoin script itself, as you suggest, but outside whereby bitcoin transactions perform the state transfer. The machine runs for as long as someone pays for it (or it goes into accepting state) - which makes sense because if there was a one-time-fee for unbounded or potentially infinite runtime, you could create a program that never terminates. This can be compared to Ethereum where every step in execution costs fees and the caller needs to ensure that a sufficient amount of fees (gas) is paid.
- truth_machine 5y ago
  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".
  - shilch 5y ago
    In Ethereum, the caller specifies the gas amount beforehand to ensure that the execution finishes. In the presented bitcoin-based solution, the caller prepares the transactions beforehand that finish the execution; it then publishes the transactions. > 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.
    - truth_machine 5y ago
      > 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.
wildsatchmo 5y ago
This is true but the conclusion is over simplified. There is of course no looping constructs in script. This is by design as it guarantees the script can be executed without consuming excessive resources. Of course it can represent a single iteration of a larger program which is the point not being acknowledged. Interesting this account is 2 hours old and seems to have been created specifically to discredit this post. At the same time, another commenter here nullc is Greg Maxwell of Blockstream fame who has become notorious for this exact behavior. These fresh accounts with long winded explanations of the same opinion tend to appear when Greg is near.
- truth_machine 5y ago
  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.
  - wildsatchmo 5y ago
    You're conflating (intentionally?) Bitcoin the system vs Bitcoin Script. Nobody claims the Script in a vacuum is Turing complete which is important and by design, including the article which clearly says "Each step in running the Turing machine is triggered by a Bitcoin transaction." Others have explained this too, so 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.
    - nullc 5y ago
      Wright himself has claimed many times that Script itself is turing complete-- in fact that is the thesis of the almost entirely plagiarized “A Proof of Turing Completeness in Bitcoin Script”, an analysis of which is linked in my long comment here. Certainly the article linked here appears to try to cause the reader to believe the same thing. > The concept of a Turing machine has been well defined. It would be sufficient to show that Bitcoin uses a dual-stack architecture that acts as a dual counter machine. Such systems have already been demonstrated as being Turing complete. Or in another article he wrote: > We demonstrate that the Bitcoin Script language allows not only for primitive recursion, but in the deployment of an Ackerman function and hence the ability to simply recurse in Bitcoin script, we show that the script system is Turing complete. Or, just a week ago, Wright wrote (https://archive.is/qztvz https://archive.is/qztvz): > Bitcoin is a Turing-complete system even in script (But we shouldn't be too surprised, since we know that Craig failed Theory of Computation-- https://twitter.com/Zectro1/status/1124185673110622208 https://twitter.com/Zectro1/status/1124185673110622208 which was arguably the only real computer science course he took in school, the rest being IT trade classes) The truthful claim he could have made instead is that script implements a universal circuit of fixed size which you can use to verify steps in transcripts of programs in TC languages... but while true, that's not novel or interesting and and been pointed out by other Bitcoiners long before Craig discovered Bitcoin. I can confirm that I don't know anything about Truth_machine here and I was initially confused by why an account name used by a well known dishonest BSV promoter to evade bans was being truthful for a change. I don't post anywhere about Bitcoin related stuff except under accounts clearly identified as me. The claim that I'm operating other accounts here isn't just unfounded, it's malicious defamation intended to protect and enable an organized campaign of fraud. Unfortunately, Wright's absurd vexatious litigation against parties that expose his fraud has caused some people to make their comments in the public interest anonymously, to reduce the risk that they are hit with a $6 billion dollar SLAPP suit (as I have been). But since you're interested in coincidences, Luke Rohenaz, perhaps you'd like to discuss with us the fact that you're here promoting BSV while being funded by Calvin Ayre a former (?) drug smuggler and indicted money launderer who spent ten years on the DHS most wanted list, and spent 20 years under a trading and director/officer ban due to operating pump&dump schemes, and whom has invested at least $300 million dollars (by his own reporting) into promoting BSV and Wright's fraud and is financing Wright's litigation in exchange for being promised a share of Bitcoin holdings which wright doesn't have access to (and never had access to).
mpapec 5y ago
Looping is not required to qualify as a Turing machine, and it never was. Bitcoin intentionally doesn't have loops, and higher level language sCrypt offer just that.

shilch 5y ago

The presented solution does *not* loop inside bitcoin script itself, as you suggest, but outside whereby bitcoin transactions perform the state transfer. The machine runs for as long as someone pays for it (or it goes into accepting state) - which makes sense because if there was a one-time-fee for unbounded or potentially infinite runtime, you could create a program that never terminates. This can be compared to Ethereum where every step in execution costs fees and the caller needs to ensure that a sufficient amount of fees (gas) is paid.

truth_machine 5y ago
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".
- shilch 5y ago
  In Ethereum, the caller specifies the gas amount beforehand to ensure that the execution finishes. In the presented bitcoin-based solution, the caller prepares the transactions beforehand that finish the execution; it then publishes the transactions. > 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.
  - truth_machine 5y ago
    > 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.

wildsatchmo 5y ago

This is true but the conclusion is over simplified. There is of course no looping constructs in script. This is by design as it guarantees the script can be executed without consuming excessive resources. Of course it can represent a single iteration of a larger program which is the point not being acknowledged. Interesting this account is 2 hours old and seems to have been created specifically to discredit this post. At the same time, another commenter here nullc is Greg Maxwell of Blockstream fame who has become notorious for this exact behavior. These fresh accounts with long winded explanations of the same opinion tend to appear when Greg is near.

truth_machine 5y ago
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.
- wildsatchmo 5y ago
  You're conflating (intentionally?) Bitcoin the system vs Bitcoin Script. Nobody claims the Script in a vacuum is Turing complete which is important and by design, including the article which clearly says "Each step in running the Turing machine is triggered by a Bitcoin transaction." Others have explained this too, so 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.
  - nullc 5y ago
    Wright himself has claimed many times that Script itself is turing complete-- in fact that is the thesis of the almost entirely plagiarized “A Proof of Turing Completeness in Bitcoin Script”, an analysis of which is linked in my long comment here. Certainly the article linked here appears to try to cause the reader to believe the same thing. > The concept of a Turing machine has been well defined. It would be sufficient to show that Bitcoin uses a dual-stack architecture that acts as a dual counter machine. Such systems have already been demonstrated as being Turing complete. Or in another article he wrote: > We demonstrate that the Bitcoin Script language allows not only for primitive recursion, but in the deployment of an Ackerman function and hence the ability to simply recurse in Bitcoin script, we show that the script system is Turing complete. Or, just a week ago, Wright wrote (https://archive.is/qztvz https://archive.is/qztvz): > Bitcoin is a Turing-complete system even in script (But we shouldn't be too surprised, since we know that Craig failed Theory of Computation-- https://twitter.com/Zectro1/status/1124185673110622208 https://twitter.com/Zectro1/status/1124185673110622208 which was arguably the only real computer science course he took in school, the rest being IT trade classes) The truthful claim he could have made instead is that script implements a universal circuit of fixed size which you can use to verify steps in transcripts of programs in TC languages... but while true, that's not novel or interesting and and been pointed out by other Bitcoiners long before Craig discovered Bitcoin. I can confirm that I don't know anything about Truth_machine here and I was initially confused by why an account name used by a well known dishonest BSV promoter to evade bans was being truthful for a change. I don't post anywhere about Bitcoin related stuff except under accounts clearly identified as me. The claim that I'm operating other accounts here isn't just unfounded, it's malicious defamation intended to protect and enable an organized campaign of fraud. Unfortunately, Wright's absurd vexatious litigation against parties that expose his fraud has caused some people to make their comments in the public interest anonymously, to reduce the risk that they are hit with a $6 billion dollar SLAPP suit (as I have been). But since you're interested in coincidences, Luke Rohenaz, perhaps you'd like to discuss with us the fact that you're here promoting BSV while being funded by Calvin Ayre a former (?) drug smuggler and indicted money launderer who spent ten years on the DHS most wanted list, and spent 20 years under a trading and director/officer ban due to operating pump&dump schemes, and whom has invested at least $300 million dollars (by his own reporting) into promoting BSV and Wright's fraud and is financing Wright's litigation in exchange for being promised a share of Bitcoin holdings which wright doesn't have access to (and never had access to).

mpapec 5y ago

Looping is not required to qualify as a Turing machine, and it never was. Bitcoin intentionally doesn't have loops, and higher level language sCrypt offer just that.