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."
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.
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".
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.
> 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.
So what is the article about, then? I started this thread disagreeing with the claim that material presented in the article somehow makes bitcoin turing complete and claiming that it, in fact, is not. You seem to be arguing this point with me, but I am not exactly sure what your (counter)arguments are.
Looping is not required to qualify as a Turing machine, and it never was.
Bitcoin intentionally doesn't have loops, and higher level language sCrypt offer just that.
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.
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.
> 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).
> The claim that I'm operating other accounts here isn't just unfounded, it's malicious defamation
Actually you have been caught at least once in sockpuppeting, so it's not a defamation rather a possible and realistic scenario which shouldn't be dismissed.
That claim is utterly false. All you're effectively doing is saying that someone has maliciously defamed me before and so it's okay to write more of it. It's not. Cut it out.
The person that page accuses of being me is a well known, highly respected community member with a decade long extremely high volume history who is utterly distinct from me-- and whos interest don't overlap mine significantly (outside of Bitcoin and the Craig Wright scam). Moreover, Wright previously admitted that contrarian__ is not me.
[Aside, mpapec is an account Craig Wright has previously used to evade his ban on HN: https://news.ycombinator.com/item?id=21978954 --- perhaps Wright out spend some time responding to his pathetic lawsuit against me instead of delaying his response and harassing me online.]
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.
You knew this already. Also, Craig's defending the claim using statements about Forth-likeness, which is the same thing he insists Bitcoin script is because magic-of-a-second-stack. Additionally, he re-iterated the exact claim that Bitcoin script itself is Turing complete with the assistance of Ian Grigg. Ian references often a paper asserting it is so, which I and two or three others completely refuted as nonsense, since the paper itself actually references another blockchain entirely which itself has looping constructs, but then Ian, Craig et al make the absurd claim that because it this other blockchain's script is "Bitcoin-like" then Bitcoin itself is therefore also Turing complete.
But then he also wrote a paper asserting that Bitcoin script is Turing complete:
In other words, it's layers of bullshit all the way down.
By the way, just for fun, Craig Wright also made the absurd assertion that the second stack can be used to create constructs that can't be implemented with a single stack, so he's stupid in that sense, too, as I demonstrated with a single sequence of single-stack opcodes which accomplishes the exact same thing he stupidly asserted couldn't be done.
> 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.<end of section>"
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.
> 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... ).
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.
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.
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.
I disagree with your stated claim on (6) which is that there is no accepting state for (M) after an arbitrary move in (5).
E.g. In bitcoin script any encounter with OP_RETURN moves you immediately into an accepting state whereupon the program halts and interpreter performs a predicate evaluation on the state of the stack.
Hopcroft et. al. also makes no claim on the input to the FSM being infinite (requiring an infinite loop). Quite the opposite. The FSM clearly reads the Program until it encounters a "simulated blank" signifying the end of input, so it can start processing the "tape".
A simpler way of satisfying the requirement of Bitcoin Script Interpreter as a 2-PDA is simply to define the State Transition function in terms of Bitcoin Script Primitives.
Q × ( ∑ ∪ {ε} ) × S × Q × S*
Where:
* Q is the finite number of states
* ∑ is input alphabet
* S is stack symbols
* q0 is the initial state (q0 ∈ Q)
* I is the initial stack top symbol (I ∈ S)
* F is a set of accepting states (F ∈ Q)
Resolving each of the above is left as an exercise to the reader.
I do concede that the actual usefulness of the computation is limited to the extent that the Bitcoin Implementation limits the size of the "input tape" i.e. the limits on size of Script.
Hence the need for Big Blocks and unbounded Script sizes to allow the market to discover the correct trade-offs between economic benefit and computational cost.
> disagree with your stated claim on (6) which is that there is no accepting state for (M) after an arbitrary move in (5).
No, this is not what I claim.
I claim that if after the step 5 the new state is not an accepting state, 2PDA has to perform another step 5 and keep doing that until an accepting state is reached, and bitcoin script cannot do "perform the step 5 until a condition is met" bit.
Could you please tell me how (in terms of opcode) the second part of the step 6 will look like, namely "Otherwise, S simulates another move of M in the same way."?
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.
Roconnor is a published expert in this domain, in fact his PHD thesis ( https://r6.ca/thesis.pdf ) was on formalizing and machine proving Gödel's incompleteness theorem. Instead, without justification or argument, you would like us to take the word of a person who failed the only theory of computation class he's taken and has been found by multiple courts to be an unreliable witness, a liar, and a forger-- a person for who has collected astounding sums on money on the promise of someday sharing some storied treasure which he-- as he's recently been forced to admit in court-- has no access to.
I see how your logic works, and I expect that most readers of this thread will as well.
Dude, you seem to have some personal beef with someone. In my above response to truth_machine I laid out a technical response on why I hold my point of view regarding the Turing Equivalence of Bitcoin.
I suggest you stick to the tech (like I'm doing), and leave the personal drama at home, 'cause I'm not interested in hearing about whatever bun-fights you are engaged in with whoever it is you're referencing above.
If you have a technical position of your own, I'd be glad to hear it. So far I've only heard appeals to the authority of a poorly-written, zero-detail, no-technical analysis opinion of someone I've never heard of until you started leaning on their opinions for claims in support of your position.
You claimed that "Bitcoin's Script Interpreter is an implementation of 2-PDA (two-stack pushdown automata)." But this is an unambiguously false claim. A two stack pushdown automata must be able to, for example, execute an infinite loop and Bitcoin's Script Interpreter cannot do this.
I've already pointed this out, so rather than repeat it I thought I would link to an expert who was speaking about exactly your claim (which is just Wright's claim), making the same argument I made.
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.
BSV and Bitcoin (BTC) are incompatible protocols, so this is just a straight out lie. Sure, it can be added to BTC as long as there's a use case and concencus for it, but so far there isn't.
> BSV and Bitcoin (BTC) are incompatible protocols
Both implementations have a large intersection. Dogecoin, Litecoin and Dash also use the bitcoin protocol and should also work.
> Sure, it can be added to BTC
The presented solution does not require a protocol change. BSV is essentially the original bitcoin protocol (with few small exception); nothing was added to the protocol to implement the turing machine. BTC has some of the scripting opcodes disabled but they can either be implemented using other opcodes (no change) or they could be reenabled as a new SegWit deployment (requires change). However, the issue you'll run into in practice is that the reference implementation (Bitcoin Core) has very small limits set and discourages scripting. You'll have to find a miner that mines the custom scripting transactions. And, well, fees are another issue.
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...
I was aware of xhliu's work before. It's actually a big thing because Ethereum was created with the assumption that bitcoin's scripting language does not allow for state transfers (stateful contracts) and turing-complete computations.
The advantage over account-based systems like Ethereum is scalability: Ethereum contracts are one central entity identified by their address, any access on the contracts must be serialised which leads to scaling issues with popular contracts. Bitcoin's UTXO model on the other hand is rather easy to parallelize; but scalable UTXO-based contracts also require a different design.
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!)
,, 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 a state change itself. Whether it's a useful addition to Bitcoin or not is another question though.
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.
Unrolling once is still what I'm referring to there.
> a new technique that was only recently developed.
That's simply false. E.g. search for 'covenant' or 'recursive covenant'. It's also described on the mailing list as far back as 2011.
(And, incidentally, the first example of a turing complete machine controlling the release of a transaction on Bitcoin was in 2016 and was vastly more efficient and private than the the approach used by the post-- https://bitcoincore.org/en/2016/02/26/zero-knowledge-conting... )
Whatever I read regarding "covenant" requires a protocol change. Independent of who described the underlying technique first, this doesn't invalidate the proof.
> The proof in the article is not about unrolling.
Sure it is. The state machine expressed in the script checks one (or more) steps of the update rule. That's what we mean by unrolling, not the "or more" part but the fact that the script is just running a simple circuit for a fixed operation.
> doesn't invalidate the proof
Proof of what? It's not a proof of script being turing complete. If you're claiming that it's that-- it's invalid on its face.
If you're saying it's a proof that script can implement a static state machine that runs one or more steps at a time checking some transcript computed by an external process and check consistency of state using the outputs-- then sure, that's not news, nor controversial, it's been known almost all of the system's life.
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.
Until you want do something completely distributed that requires trust. The runtime isn't great, but then again, what runtime is better that meets those requirements? ACH is far slower than many blockchain solutions, for example.
For what it’s worth I think that if people were downvoting you because of your position, they would be downvoting the parent as well. They’re downvoting you because saying “I was going to say the same thing” doesn’t contribute to the conversation.
Two things: 1) 'me-too' comments tend to get downvoted here in an effort to promote substantive discussion. I think something gets lost in the gulf between an upvote and stating you agree but thems the breaks and 2) cryptocurrencies actually do get used by people that lack access to stable currencies. I asked about this myself. I don't think it changes the original assessment, but it is heartening to know that there is some real utility people are getting out of this tech.
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.
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
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?
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.
> 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.
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).
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.
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."