from Hacker News

Turing Machines on Bitcoin

by GBiT on 9/18/21, 8:12 AM with 66 comments

  • by truth_machine on 9/19/21, 7:44 PM

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

  • by tromp on 9/18/21, 9:04 AM

    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.

  • by xiphias2 on 9/19/21, 5:00 PM

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

  • by reginold on 9/19/21, 5:18 PM

    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

  • by nullc on 9/19/21, 8:49 PM

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

  • by davidcbc on 9/19/21, 4:57 PM

    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.

  • by etaioinshrdlu on 9/19/21, 7:22 PM

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