Quote from: YarkoL on December 14, 2015, 09:25:56 AM

Quote from: TPTB_need_war on December 13, 2015, 10:41:22 PM

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.

Wright explicitly stated that he wasn't claiming the script can loop, but that factors orthogonal to the scripting can implement the paradigm of looping. His point is the Bitcoin block chain stack is already Turing-complete. And on that point he is correct, because the entropy of the block chain state is unbounded. Anything that can be done with Ethereum due to Turing-completeness which is not an attack on scripting node resources, can also theoretically (in terms of asymptotic computational complexity theory) be done on the Bitcoin block chain.

But remember from my Overview section that intuitions from computational complexity theory are not an absolute guarantee of how it works out in the real world implementation.

So there are real world implementation differences in efficiency, practicality, atomicity, and storage/state per transaction comparing Bitcoin and Ethereum. And I don't claim to be very knowledgeable about the scripting capabilities of either rather I am just speaking from a high level conceptual view.

For example, there are some protections gained from making the scripting deterministic (bounded with provable termination), such as the verification nodes can be sure the script will terminate (but even that alone doesn't prevent the script from consuming too many verification resources). Specifically the Bitcoin scripting node algorithms are (in a non-boolean variant of) P. So in that sense there is asymptotic complexity distinction between Bitcoin and Ethereum, except that Ethereum uses "gas" to be sure scripts terminate so it is in ~~P also (and thus the Ethereum scripts are not Turing-complete either apparently but don't quote me on that because I haven't studied Ethereum's scripting)~~[on further thought Ethereum scripts are in some variant related to RP complexity because the termination due to "gas" is an "I don't know" result].

I am stating that Szabo and Maxwell have conflated Turing-completeness with differences in efficiency, practicality, atomicity, and storage/state per transaction.

Conflating an asymptotic attribute (computational complexity) with a set of non-asymptotic attributes (efficiency, practicality, atomicity, and per txn storage/state) is akin to not understanding computational complexity. Which is strange because I know Szabo and Maxwell do both understand. They probably didn't intend to conflate. They've had their minds deep in many issues and just didn't take some moments to deeply think about it. I happened to be writing about this, so my mind was very focused on the distinction.