Comment by stephanfeb | Hacker News Reader

Comment by stephanfeb | Hacker News Reader

Parent Full thread

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

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

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.

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.

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.

Reply on news.ycombinator.com