stephanfeb

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

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 ?

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