Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Turing Machines on Bitcoin

xiaohuiliu.medium.com

Post reply on HN
Print view View original

41–50 of 80 posts

Re: Turing Machines on Bitcoin

#41

Post by truth_machine »

wildsatchmo wrote: post #39
truth_machine wrote: post #20

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 comp…

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…

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.

Re: Turing Machines on Bitcoin

#42

Post by [deleted] »

wildsatchmo wrote: post #39
truth_machine wrote: post #20

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 comp…

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…

[deleted]

Re: Turing Machines on Bitcoin

#43

Post by wildsatchmo »

truth_machine wrote: post #41
wildsatchmo wrote: post #39

Earlier quoted context omitted.

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…

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.

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.

Re: Turing Machines on Bitcoin

#44

Post by nullc »

wildsatchmo wrote: post #43
truth_machine wrote: post #41

Earlier quoted context omitted.

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.

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 pec…

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):

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

Re: Turing Machines on Bitcoin

#45

Post by wildsatchmo »

nullc wrote: post #44
wildsatchmo wrote: post #43

Earlier quoted context omitted.

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 pec…

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 suffici…

Here is CSW's original claim that Bitcoin is Turing complete that took many by surprise including Nick Szabo. They heard it as you did, specifically addressing Bitcoin Script.

He immediately corrects them:

"The difference is that the SCRIPT ITSELF ISN'T, what you can do is..."

So there you go. Clearly not what you're claiming here, and if he said anything similar casually I'm sure this is exactly what he means, as he has stated many times, as the article states, as others have stated, as I understand it, and as can be observed.

https://youtu.be/LdvQTwjVmrE?t=1083

I'm glad to hear you never post under other accounts.

Re: Turing Machines on Bitcoin

#46

Post by tombeak »

truth_machine wrote: post #41
wildsatchmo wrote: post #39

Earlier quoted context omitted.

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…

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.

Have you watched this short clip? It may clear your misunderstanding of the topic. https://www.youtube.com/watch?v=MwGRfJ0L5eQ

Re: Turing Machines on Bitcoin

#47

Post by stephanfeb »

truth_machine wrote: post #22
tromp wrote: post #2

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.

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…

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

Re: Turing Machines on Bitcoin

#48

Post by lolthishuman »

nullc wrote: post #31

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…

After reading that medium article on the plagiarism, it made me have a weird thought.

Craig kind of acts like a GPT-3 copyright utility function. It’s as if he’s scouring all content as a wild GAN patent troll. Even using past published papers to be rewritten under a copyright handle. Even the translation has errors related to visual artifacts vs human vision. Odd.

Re: Turing Machines on Bitcoin

#49

Post by shilch »

nullc wrote: post #36
xiphias2 wrote: post #35

Earlier quoted context omitted.

,, 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.'' 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…

What the article is describing-- explicitly unrolling operations in advance and checking them in script-- has always been possible in Bitcoin and doesn't have anything to do with Turing completeness. It's only being promoted as something new or inventive as an element of a very strange con.

This is not at all what this article describes. You're making the same mistake as truth_machine does: The loop unrolling is not part of the proof but just an implementation detail for the transition lookup; it could as well have been a large if-else. The actual looping / transitioning is implemented via bitcoin transactions which is a new technique that was only recently developed.

Re: Turing Machines on Bitcoin

#50

Post by shilch »

truth_machine wrote: post #33
shilch wrote: post #30

Earlier quoted context omitted.

Then you either misunderstand or (intentionally?) misrepresent the article. The `loop` construct you're talking about has nothing to do with the author's proof, and neither does it "essentially use bitcoin blockchain as a database" as you have written somewhere else in the thread. For the interested reader, I have commented on these points where they were brought up. To explain the Game of Life contract you're linkin…

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…

The loop unrolling is an implementation detail. As I have written somewhere else: You could as well have put a large if-else there to do the transition table lookup.

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.

Post reply on HN