Does the alternative stack make Script Turing complete?

Question

The wiki documents the presence of an "alt stack" in Script:

• OP_TOALTSTACK Puts the input onto the top of the alt stack. Removes it from the main stack.
• OP_FROMALTSTACK Puts the input onto the top of the main stack. Removes it from the alt stack.

It appears then that Script may qualify as a Two-Stack Pushdown Automaton. And this system is known to be equivalent to a Turing Machine. For example:

To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. Start by pushing the normal "bottom of stack" markers on both stacks, then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

https://cs.stackexchange.com/questions/2832/is-a-push-down-automaton-with-two-stacks-equivalent-to-a-turing-machine/2833#2833

Wikipedia defines "Turing complete" as:

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.

https://en.wikipedia.org/wiki/Turing_completeness

This thread makes reference to the alt stack, claiming that its presence makes Script Turing complete:

https://www.reddit.com/r/Bitcoin/comments/7yb3is/where_is_the_evidence_that_bitcoin_is_turing/duf1rt9/

That thread links to this thread, which contains the following:

While it is a well known CS result that a two-stack push-down automata has the same power as a Turing Machine, Bitcoin Script cannot operate as a two-stack push-down automata. Even though Bitcoin Script has two stacks, Bitcoin Script doesn't have an associated finite state machine that you can create.

https://reddit.com/r/btc/comments/6hjxiy/new_craig_wright_interview_part_2_on/diz9g69/?context=3

In other words, there may be two stacks, but there's no way to sufficiently power them to create a Turing Machine.

Is Bitcoin Script Turing complete given the presence of the alt stack? If not, what specific functionality is missing?

Answer 1

No, the alt-stack doesn't make bitcoin script a Turing-complete language.

While script has two stacks, in order to simulate a two-stack pushdown automata (which is Turing complete), one has to be able to implement a finite-state control unit. This cannot be done in bitcoin script, since there is no looping or conditional branching available. It is possible to write a script that goes through the motions of running a Turing machine program by unrolling loops, but that will only work for a machine and input combination that terminates. It is very simple to write a Turing machine with a finite input string that loops indefinitely eg. consider the Turing machine defined by

states: q0 (initial), q1 and q3 (final)

and tape alphabet {0, 1}

where the transitions are

(q0, 0) -> (q1, 0, move left)

(q1, 0) -> (q1, 0, move left)

(q1, 1) -> (q1, 1, move right)

Given input 01, this machine will just loop infinitely, as simulated here:

http://turingmachinesimulator.com/shared/ojvubpsgkm

Attempting to "unroll" this as a bitcoin script will never finish.

Answer 2

You may be interested in a post I wrote. I wrote a Turing Machine (by utilizing the two stacks) and made a test transaction.

Basically if we assume that our program will halt, then it requires only a finite number of instructions, which is supported by the Bitcoin script. Unfortunately the Bitcoin script VM only allows a limited number of operations to be executed so only very short programs can be written in practice.

Answer 3

Yes but sometimes clarke the bitcoin source of Autoscope interesting, sometimes we need to see the beginning of the first things of the next.

Confirmation of none technical aim can terminate me asking task bitcoin interested layer at low @ understanding per jam dot net.

where the transitions are

(q0, 0) -> (q1, 0, move left)

(q1, 0) -> (q1, 0, move left)

(q1, 1) -> (q1, 1, move right)

Given also input 01 urgent. thanks