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

61–70 of 80 posts

Re: Turing Machines on Bitcoin

#61

Post by nullc »

stephanfeb wrote: post #47
truth_machine wrote: post #22

Earlier quoted context omitted.

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…

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

Re: Turing Machines on Bitcoin

#62

Post by nullc »

tombeak wrote: post #46
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.

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

Better to watch this short clip, which debunks the above clip point by point: https://www.dailymotion.com/video/x7y4gch

Re: Turing Machines on Bitcoin

#63

Post by truth_machine »

shilch wrote: post #50
truth_machine wrote: post #33

Earlier quoted context omitted.

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

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.

Re: Turing Machines on Bitcoin

#64

Post by truth_machine »

stephanfeb wrote: post #47
truth_machine wrote: post #22

Earlier quoted context omitted.

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…

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.

Re: Turing Machines on Bitcoin

#65

Post by shilch »

truth_machine wrote: post #63
shilch wrote: post #50

Earlier quoted context omitted.

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

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

> because bitcoin script is not turing-complete

This is not what the article claims to show. It shows that the system bitcoin is turing complete.

Added to this, having an "external driver" and the system being turing-complete are not mutually exclusive.

Re: Turing Machines on Bitcoin

#66

Post by truth_machine »

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…

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

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.

Re: Turing Machines on Bitcoin

#67

Post by truth_machine »

shilch wrote: post #65
truth_machine wrote: post #63

Earlier quoted context omitted.

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

> because bitcoin script is not turing-complete This is not what the article claims to show. It shows that the system bitcoin is turing complete. Added to this, having an "external driver" and the system being turing-complete are not mutually exclusive.

What is "bitcoin system"?

Re: Turing Machines on Bitcoin

#68

Post by tombeak »

nullc wrote: post #62
tombeak wrote: post #46

Earlier quoted context omitted.

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

Better to watch this short clip, which debunks the above clip point by point: https://www.dailymotion.com/video/x7y4gch

https://craigwright.net/blog/math/infinite-and-unbounded/

Re: Turing Machines on Bitcoin

#69

Post by nullc »

tombeak wrote: post #68
nullc wrote: post #62

Earlier quoted context omitted.

Better to watch this short clip, which debunks the above clip point by point: https://www.dailymotion.com/video/x7y4gch

https://craigwright.net/blog/math/infinite-and-unbounded/

Compare that article:

> Shannon (1956) looked at the concept provided by Turing to make a mechanical or other electric machine and made an error in the description. Unfortunately, Shannon described Turing's machine as a system that requires "a control element, a reading and writing head, and an infinite tape". It was not Turing that stated that a Turing machine must be infinite but rather Shannon. Whilst Shannon produced some excellent engineering; he was not a mathematician. -- Craig (Fraudtoshi) Wright

to

> Some years ago I was researching on what might now be described as an investigation of the theoretical possibilities and limitations of digital computing machines. I considered a type of machine which had a central mechanism, and an infinite memory which was contained on an infinite tape. This type of machine appeared to be sufficiently general. One of my conclusions was that the idea of a 'rule of thumb' process and a 'machine process' were synonymous. The expression 'machine process' of course means one which could be carried out by the type of machine I was considering. lt was essential in these theoretical arguments that the memory should be infinite. It can easily be shown that otherwise the machine can only execute periodic operations. -- Lecture to the London Mathematical Society, Alan Turing, 1947

Turing himself directly refutes Wright's nonsense and did so over 70 years ago.

Wright also claims that Shannon wasn't a mathematician... but Shannon's PHD was in Mathematics! ... and isn't it usually engineers who dispense with the infinities? ... Wright better let the NYT know than Shannon wasn't a mathematician ( https://www.nytimes.com/2001/02/27/nyregion/claude-shannon-m... ).

Re: Turing Machines on Bitcoin

#70

Post by stephanfeb »

nullc wrote: post #61
stephanfeb wrote: post #47

Earlier quoted context omitted.

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…

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_wrigh... In Bitcoin script the additional stack doesn't increase its computational power at all: Ignoring the…

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 ?

Post reply on HN