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

21–30 of 80 posts

Re: Turing Machines on Bitcoin

#21

Post by shilch »

dane-pgp wrote: post #13
shilch wrote: post #9

Earlier quoted context omitted.

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.

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

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

Re: Turing Machines on Bitcoin

#22

Post by truth_machine »

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

Re: Turing Machines on Bitcoin

#23

Post by shilch »

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…

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.

Re: Turing Machines on Bitcoin

#24

Post by truth_machine »

etaioinshrdlu wrote: post #17

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

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.

Re: Turing Machines on Bitcoin

#25

Post by shilch »

etaioinshrdlu wrote: post #17

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

These are two separate things. The `loop` construction / function or whatever it is called in the sCrypt language is a compile-time loop. That is, the body gets unrolled N times (8 in this example). It's just an implementation detail for the lookup in the transition table. However, that is not part of a proof. The author is pretty clear that each transition in the TM is implemented as a bitcoin transaction.

Re: Turing Machines on Bitcoin

#26

Post by truth_machine »

shilch wrote: post #23
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…

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

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

Re: Turing Machines on Bitcoin

#27

Post by shilch »

truth_machine wrote: post #24
etaioinshrdlu wrote: post #17

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

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

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

Re: Turing Machines on Bitcoin

#28

Post by truth_machine »

shilch wrote: post #27
truth_machine wrote: post #24

Earlier quoted context omitted.

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

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

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

Re: Turing Machines on Bitcoin

#29

Post by shilch »

truth_machine wrote: post #26
shilch wrote: post #23

Earlier quoted context omitted.

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

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

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.

Re: Turing Machines on Bitcoin

#30

Post by shilch »

truth_machine wrote: post #28
shilch wrote: post #27

Earlier quoted context omitted.

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

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 "Bitco…

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 linking to: The `loop`, again, is just an implementation detail to go over each field on the board in a *single* transaction. It's not part of any proof. The actual turing-complete element - letting the GoL run - happens outside: Each generation state transfer happens via a bitcoin transaction.

Post reply on HN