At roughly the
17 minute mark in this conference video, Wright correctly explains that due to unbounded recursion, the Bitcoin block chain scripting is effectively Turing-complete. Afaics, he is entirely correct and Nick Szabo is wrong, because although the scripting language stack can't loop within one transaction, one can use multiple transactions to simulate looping. This is precisely the point I made in my recent post wherein I explained that under composition it is impossible to prevent unbounded recursion and thus unbounded entropy. Review the Dr. Suess proof of Turing-completeness. It doesn't matter what the called script answers, the calling script can always change the outcome. If you have the ability to store state on the block chain across multiple invocations of a script, then the block chain becomes the stack. Nick Szabo just demonstrated to me that he isn't as smart as I thought. Dr. Wright makes a relevant point that many people these days seem to forget that in machine code there is no virtual machine that controls what the instruction set can do in terms of which memory it can treat as a stack. Bitcoin's script instruction set can be viewed as machine code w.r.t. to its ability to read and store state any where in the memory space of the block chain UTXO.
You can use the blockchain as a stack (using embedded metadata),
but then it is being manipulated by the client, not by the script.
The script works in the context of a single transaction and does not
know about the blockchain.
Just as a single transaction is a part of the entire blockchain,
the script engine is a submodule of the client. They are on
different logical levels*. The client can loop, the script can't.
_____
*) I use the term "logical level" in the same sense as Russell
and Whitehead did when they resolved the set-of-all-sets paradox
by establishing that it makes no sense to call the collection of
all sets a set, as it is on "higher" logical level or context.