10 ms·

Turing Machines on Bitcoin

44 points by GBiT 5y ago

tromp 5y ago
With a separate transaction (over 6KB in size in their small example TM) needed for every TM transition, this can get rather expensive in fees. Except when you run it on Bitcoin BSV as they did.
- truth_machine 5y ago
  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.
  - stephanfeb 5y ago
    Where looping is concerned, you can either externalise the cost of looping by requiring some other entity with more resources to perform your computation for you, or you can pay upfront and commit satoshis to your computation. Regardless, you're still looping. 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/S0019995866800037 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/machine-push-automata-2-stacks-diagram-example-push-automata-pda-two-stacks-septuple-m-k-1-q34191104 https://www.chegg.com/homework-help/questions-and-answers/ma...
    - nullc 5y ago
      Thanks for giving us a concrete in-thread example of a person claiming the script interpreter is turing complete. 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_wright_interview_part_2_on/diz9g69/ 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.
      - stephanfeb 5y ago
        I disagree with @roconnor's assessment in the link provided. Just like that, I've "discredited" @roconnor. 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 ?
        nullc 5y ago
        Roconnor explains his position, you do not. Roconnor is a published expert in this domain, in fact his PHD thesis ( https://r6.ca/thesis.pdf 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.
        stephanfeb 5y ago
        Dude, you seem to have some personal beef with someone. In my above response to truth_machine I laid out a technical response on why I hold my point of view regarding the Turing Equivalence of Bitcoin. 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.
davidcbc 5y ago
This is the perfect representative of blockchain technology because it’s a convoluted way to do something that is better done with existing technologies without using a blockchain.
- p4bl0 5y ago
  I'm glad I hit the reload button before writing my comment, I was going to say the exact same thing. EDIT: Okay blockchain zealots, downvote and flag my comment all you want, but if for once one of you could actually show a project that uses a blockchain (other than so-called "cryptocurrencies" which are essentially used as a speculation asset) and which cannot be implemented better and more efficiently with other technologies, that might be a little more interesting.
  - fogof 5y ago
    For what it’s worth I think that if people were downvoting you because of your position, they would be downvoting the parent as well. They’re downvoting you because saying “I was going to say the same thing” doesn’t contribute to the conversation.
  - burnished 5y ago
    Two things: 1) 'me-too' comments tend to get downvoted here in an effort to promote substantive discussion. I think something gets lost in the gulf between an upvote and stating you agree but thems the breaks and 2) cryptocurrencies actually do get used by people that lack access to stable currencies. I asked about this myself. I don't think it changes the original assessment, but it is heartening to know that there is some real utility people are getting out of this tech.
- toolz 5y ago
  Until you want do something completely distributed that requires trust. The runtime isn't great, but then again, what runtime is better that meets those requirements? ACH is far slower than many blockchain solutions, for example.
  - 5y ago
xiphias2 5y ago
This is about Bitcoin SV (BSV), not Bitcoin (BTC)
- dominojab 5y ago
  show me where in the whitepaper there is a limit to the block size defined as a unchangeable spec.
- shilch 5y ago
  The solution presented in the article uses the bitcoin protocol. BSV is just one implementation of that. It could also work on BCH if some default limits were lifted, and (theoretically, not economically) possible on BTC.
  - dane-pgp 5y ago
    > It could also work on BCH if some default limits were lifted Can you list what those default limits are, and how big the needed changes are?
    - shilch 5y ago
      I just wrote the comment and noticed that the scripting limits on BCH are actually a network rule and are not miner-configurable. So my statement that "it could also work on BCH if some default limits were lifted" is only correct in the sense that this number needs to be increased in a network upgrade: https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/blob/master/src/script/script.h#L26 https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/blo...
  - xiphias2 5y ago
    BSV and Bitcoin (BTC) are incompatible protocols, so this is just a straight out lie. Sure, it can be added to BTC as long as there's a use case and concencus for it, but so far there isn't.
    - shilch 5y ago
reginold 5y ago
Could someone who likes this article share what they liked about it? 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
- shilch 5y ago
  I was aware of xhliu's work before. It's actually a big thing because Ethereum was created with the assumption that bitcoin's scripting language does not allow for state transfers (stateful contracts) and turing-complete computations. The advantage over account-based systems like Ethereum is scalability: Ethereum contracts are one central entity identified by their address, any access on the contracts must be serialised which leads to scaling issues with popular contracts. Bitcoin's UTXO model on the other hand is rather easy to parallelize; but scalable UTXO-based contracts also require a different design.
  - deleted 5y ago
    [deleted]
lolthishuman 5y ago
What’s the point?
etaioinshrdlu 5y ago
The loop only has 8 iterations. Doesn’t look particularly turing complete.
- truth_machine 5y ago
  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.
  - shilch 5y ago
    I don't know what you're up to; your account is 30min old, was created just for commenting on this post, you appear to be very aware of this project and your comments show that you didn't understand the solution presented in the article. I already commented on the parent comment: The `loop` in sCrypt is a compile-time loop and just an implementation detail for the lookup in the transition table. The *actual looping* happens outside via bitcoin transactions whereby each transaction is a transition in the TM. https://news.ycombinator.com/item?id=28587465 https://news.ycombinator.com/item?id=28587465
    - truth_machine 5y ago
      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? 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-bitcoin-forever-47c6fb7ed682 https://xiaohuiliu.medium.com/play-conways-game-of-life-on-b... and https://xiaohuiliu.medium.com/turing-complete-rule-110-on-bitcoin-df014288a05 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.
bob229 5y ago
Blockchain is for cranks
truth_machine 5y ago
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".
nullc 5y ago
This post is making fraudulent claims for the purpose of promoting the court adjudicated conman Craig Wright and his scam Bitcoin knockoff, "Bitcoin Satoshi Vision". 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-dive-into-one-of-craig-wrights-plagiarized-papers-96bc8624fc12 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://www.youtube.com/watch?v=TGE6jrVmt_I / https://cyber.stanford.edu/sites/default/files/russelloconnor.pdf 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/ https://www.reddit.com/r/bsvscam/ and https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-make-wright https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-m...
someonewhocar3s 5y ago
1. The miners don't run your code 2. The network has no incentive to run your code 3. You are interpreting your code (original sw ignores it) Having a third party app checkpoint and do TX to log that is operationally the same. A hash does anchor what's from very well. I'd therefor avoid arguing 'bitcoin is turing complete'. Somehow I feel they're arguing it doesn't matter. I also note the lack of a Bitcoin opcode sample. "Ramming Memory in to BTC" is as far as they went.

44 points by GBiT 5y ago

With a separate transaction (over 6KB in size in their small example TM) needed for every TM transition, this can get rather expensive in fees. Except when you run it on Bitcoin BSV as they did.

truth_machine 5y ago
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.
- stephanfeb 5y ago
  Where looping is concerned, you can either externalise the cost of looping by requiring some other entity with more resources to perform your computation for you, or you can pay upfront and commit satoshis to your computation. Regardless, you're still looping. 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/S0019995866800037 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/machine-push-automata-2-stacks-diagram-example-push-automata-pda-two-stacks-septuple-m-k-1-q34191104 https://www.chegg.com/homework-help/questions-and-answers/ma...
  - nullc 5y ago
    Thanks for giving us a concrete in-thread example of a person claiming the script interpreter is turing complete. 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_wright_interview_part_2_on/diz9g69/ 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.
    - stephanfeb 5y ago
      I disagree with @roconnor's assessment in the link provided. Just like that, I've "discredited" @roconnor. 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 ?
      - nullc 5y ago
        Roconnor explains his position, you do not. Roconnor is a published expert in this domain, in fact his PHD thesis ( https://r6.ca/thesis.pdf 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.
        stephanfeb 5y ago
        Dude, you seem to have some personal beef with someone. In my above response to truth_machine I laid out a technical response on why I hold my point of view regarding the Turing Equivalence of Bitcoin. 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.

davidcbc 5y ago

This is the perfect representative of blockchain technology because it’s a convoluted way to do something that is better done with existing technologies without using a blockchain.

p4bl0 5y ago
I'm glad I hit the reload button before writing my comment, I was going to say the exact same thing. EDIT: Okay blockchain zealots, downvote and flag my comment all you want, but if for once one of you could actually show a project that uses a blockchain (other than so-called "cryptocurrencies" which are essentially used as a speculation asset) and which cannot be implemented better and more efficiently with other technologies, that might be a little more interesting.
- fogof 5y ago
  For what it’s worth I think that if people were downvoting you because of your position, they would be downvoting the parent as well. They’re downvoting you because saying “I was going to say the same thing” doesn’t contribute to the conversation.
- burnished 5y ago
  Two things: 1) 'me-too' comments tend to get downvoted here in an effort to promote substantive discussion. I think something gets lost in the gulf between an upvote and stating you agree but thems the breaks and 2) cryptocurrencies actually do get used by people that lack access to stable currencies. I asked about this myself. I don't think it changes the original assessment, but it is heartening to know that there is some real utility people are getting out of this tech.
toolz 5y ago
Until you want do something completely distributed that requires trust. The runtime isn't great, but then again, what runtime is better that meets those requirements? ACH is far slower than many blockchain solutions, for example.
- 5y ago

xiphias2 5y ago

This is about Bitcoin SV (BSV), not Bitcoin (BTC)

dominojab 5y ago
show me where in the whitepaper there is a limit to the block size defined as a unchangeable spec.
shilch 5y ago
The solution presented in the article uses the bitcoin protocol. BSV is just one implementation of that. It could also work on BCH if some default limits were lifted, and (theoretically, not economically) possible on BTC.
- dane-pgp 5y ago
  > It could also work on BCH if some default limits were lifted Can you list what those default limits are, and how big the needed changes are?
  - shilch 5y ago
    I just wrote the comment and noticed that the scripting limits on BCH are actually a network rule and are not miner-configurable. So my statement that "it could also work on BCH if some default limits were lifted" is only correct in the sense that this number needs to be increased in a network upgrade: https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/blob/master/src/script/script.h#L26 https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/blo...
- xiphias2 5y ago
  BSV and Bitcoin (BTC) are incompatible protocols, so this is just a straight out lie. Sure, it can be added to BTC as long as there's a use case and concencus for it, but so far there isn't.
  - shilch 5y ago

reginold 5y ago

Could someone who likes this article share what they liked about it? 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

shilch 5y ago
I was aware of xhliu's work before. It's actually a big thing because Ethereum was created with the assumption that bitcoin's scripting language does not allow for state transfers (stateful contracts) and turing-complete computations. The advantage over account-based systems like Ethereum is scalability: Ethereum contracts are one central entity identified by their address, any access on the contracts must be serialised which leads to scaling issues with popular contracts. Bitcoin's UTXO model on the other hand is rather easy to parallelize; but scalable UTXO-based contracts also require a different design.
- deleted 5y ago
  [deleted]

lolthishuman 5y ago

What’s the point?

etaioinshrdlu 5y ago

The loop only has 8 iterations. Doesn’t look particularly turing complete.

truth_machine 5y ago
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.
- shilch 5y ago
  I don't know what you're up to; your account is 30min old, was created just for commenting on this post, you appear to be very aware of this project and your comments show that you didn't understand the solution presented in the article. I already commented on the parent comment: The `loop` in sCrypt is a compile-time loop and just an implementation detail for the lookup in the transition table. The *actual looping* happens outside via bitcoin transactions whereby each transaction is a transition in the TM. https://news.ycombinator.com/item?id=28587465 https://news.ycombinator.com/item?id=28587465
  - truth_machine 5y ago
    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? 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-bitcoin-forever-47c6fb7ed682 https://xiaohuiliu.medium.com/play-conways-game-of-life-on-b... and https://xiaohuiliu.medium.com/turing-complete-rule-110-on-bitcoin-df014288a05 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.

bob229 5y ago

Blockchain is for cranks

truth_machine 5y ago

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

nullc 5y ago

This post is making fraudulent claims for the purpose of promoting the court adjudicated conman Craig Wright and his scam Bitcoin knockoff, "Bitcoin Satoshi Vision". 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-dive-into-one-of-craig-wrights-plagiarized-papers-96bc8624fc12 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://www.youtube.com/watch?v=TGE6jrVmt_I / https://cyber.stanford.edu/sites/default/files/russelloconnor.pdf 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/ https://www.reddit.com/r/bsvscam/ and https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-make-wright https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-m...

someonewhocar3s 5y ago

1. The miners don't run your code 2. The network has no incentive to run your code 3. You are interpreting your code (original sw ignores it) Having a third party app checkpoint and do TX to log that is operationally the same. A hash does anchor what's from very well. I'd therefor avoid arguing 'bitcoin is turing complete'. Somehow I feel they're arguing it doesn't matter. I also note the lack of a Bitcoin opcode sample. "Ramming Memory in to BTC" is as far as they went.