The wiki documents the presence of an "alt stack" in Script:
OP_TOALTSTACKPuts the input onto the top of the alt stack. Removes it from the main stack.
OP_FROMALTSTACKPuts 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.
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.
This thread makes reference to the alt stack, claiming that its presence makes Script Turing complete:
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.
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?