Turing Machines on Bitcoin(xiaohuiliu.medium.com)
xiaohuiliu.medium.com
Turing Machines on Bitcoin
https://xiaohuiliu.medium.com/turing-machine-on-bitcoin-7f0ebe0d52b1
10 comments
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".
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.
> 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.
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.
wildsatchmo(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.
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.
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...
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...
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.
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.
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."?
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."?
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.
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.
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 ?
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 ?
Roconnor explains his position, you do not.
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.
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.
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.
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.
This is about Bitcoin SV (BSV), not Bitcoin (BTC)
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?
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...
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.
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.
Could someone who likes this article share what they liked about it?
I'm getting the idea that it's either 1. A fun proof of principle project 2. entertains more "compute" ideas on blockchains, kinda like Ethereum
I'm getting the idea that it's either 1. A fun proof of principle project 2. entertains more "compute" ideas on blockchains, kinda like Ethereum
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.
[deleted]
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!)
For more information on the BSV scam and Wright's fraudulent claims checkout https://www.reddit.com/r/bsvscam/ and https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-m...
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!)
For more information on the BSV scam and Wright's fraudulent claims checkout https://www.reddit.com/r/bsvscam/ and https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-m...
,, 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.
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.
> The loop unrolling
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... )
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... )
The proof in the article is not about unrolling.
Whatever I read regarding "covenant" requires a protocol change. Independent of who described the underlying technique first, this doesn't invalidate the proof.
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.
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.
It's actually not possible on BTC
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.
p4bl0(2)
"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something."
https://news.ycombinator.com/newsguidelines.html
https://news.ycombinator.com/newsguidelines.html
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.
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?
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.
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.
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
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.
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.
> 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.
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.
> 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.
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.
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
But you can just post it in the comment here, I will see it
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."