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

71–80 of 80 posts

Re: Turing Machines on Bitcoin

#71

Post by stephanfeb »

truth_machine wrote: post #64
stephanfeb wrote: post #47

Earlier quoted context omitted.

Where looping is concerned, you can either externalise the cost of looping by requiring some other entity with more resources to perform your computation for you, or you can pay upfront and commit satoshis to your computation. Regardless, you're still looping. All that is moot in my opinion though. The issue was settled a long time ago before Bitcoin's founding. “If a language L is accepted by a Turing Machine, then…

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

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.

Re: Turing Machines on Bitcoin

#72

Post by shilch »

truth_machine wrote: post #67
shilch wrote: post #65

Earlier quoted context omitted.

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

Re: Turing Machines on Bitcoin

#73

Post by nullc »

stephanfeb wrote: post #70
nullc wrote: post #61

Earlier quoted context omitted.

Thanks for giving us a concrete in-thread example of a person claiming the script interpreter is turing complete. The claim you're making regarding "two stacks" is technobabble initially created by Wright which was clearly discredited many years ago, e.g. https://www.reddit.com/r/btc/comments/6hjxiy/new_craig_wrigh... In Bitcoin script the additional stack doesn't increase its computational power at all: Ignoring the…

I disagree with @roconnor's assessment in the link provided. Just like that, I've "discredited" @roconnor. Folks are now free to reference this link in future posts as a claim that @roconnor's post has been discredited. See how that logic works ?

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.

Re: Turing Machines on Bitcoin

#74

Post by stephanfeb »

nullc wrote: post #73
stephanfeb wrote: post #70

Earlier quoted context omitted.

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 ?

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

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.

Re: Turing Machines on Bitcoin

#75

Post by nullc »

stephanfeb wrote: post #74
nullc wrote: post #73

Earlier quoted context omitted.

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

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

Re: Turing Machines on Bitcoin

#76

Post by truth_machine »

stephanfeb wrote: post #71
truth_machine wrote: post #64

Earlier quoted context omitted.

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

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

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

Re: Turing Machines on Bitcoin

#77

Post by truth_machine »

shilch wrote: post #72
truth_machine wrote: post #67

Earlier quoted context omitted.

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

Re: Turing Machines on Bitcoin

#78

Post by CrackheadWright »

stephanfeb wrote: post #74
nullc wrote: post #73

Earlier quoted context omitted.

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

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…

This ought to be incredibly easy to show. Just write a simple (finitely long) Script program that enters an infinite loop and never terminates.

If you can't do that, Script cannot be Turing complete.

Re: Turing Machines on Bitcoin

#79

Post by CrackheadWright »

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

Earlier quoted context omitted.

Sorry, but the (max) board size is not known in advance. Board grows as the Turing machine simulator is running. > What you can then do instead is, for example, to update the first half of the board in one transaction and then the second half in another transaction, i.e. two transactions are one generation Yes, we just need to add the external "driver" that partitions the board, determines the bounds of board parts,…

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

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

Re: Turing Machines on Bitcoin

#80

Post by shilch »

truth_machine wrote: post #77
shilch wrote: post #72

Earlier quoted context omitted.

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/
Post reply on HN