Comment by truth_machine | Hacker News Reader

Comment by truth_machine | Hacker News Reader

Parent Full thread

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.

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.

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 (b)article provides implementation of GoL board in sCrypt, therefore "Bitcoin in turing-complete". However, the board in article is limited (due to loop inlining) and cannot be made 1000s x 1000s (as required for the simulation of the turing machine) precisely because of the loop unrolling. I also note that author does not point out this limitation (in any of his articles, it seems) - the claims are always "we can simulate Game of Life, we can do Machine Learning, we can simulate Rule 110 automata" without any mention that these are toy examples that hardly do anything and can't scale even by an order of magnitude. So loop is indeed an implementation detail, but quite essential one, it seems.

2. More broadly, I am agruing against the claim that "Bitcoin is turing complete" made in this and other articles by the same author. But, again, it seems that on this point we are actually in agreement

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.

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.

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

I might write an article that explains it (if I find the time to do so). The thread form of back and forth is fruitless since it appears that we don't have a common understanding of what makes bitcoin turing complete. Let me know how I can reach you back if I have written such article (and you're interested).

If you have written such an article and it is sound, I would imagine that I would hear it all during your Alan Turing award lecture :)

But you can just post it in the comment here, I will see it

Here you go: https://shilch.me/bitcoin-turing-complete/

> having an "external driver" and the system being turing-complete are not mutually exclusive.

In many cases, they are. For instance, if you tack on an already-Turing-complete component to the existing "system", then it's disingenuous to call the existing system Turing complete.

Further, this "covenant"-style system isn't really what Turing had in mind when he spoke of an "automatic machine".

Further further, this has nothing to do with Craig Wright, who famously called Script itself Turing complete in a plagiarized paper, and said that the "alt stack" is critical for it to be Turing complete.

Nonsense.

Reply on news.ycombinator.com