Does the alternative stack make Script Turing complete? 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?
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.