I have been skeptical about Turing complete on chain computation for a long time. Many early proponents took the position that there is no issue because a mechanism such as Ethereum’s gas limits how long a computation can run. They argued that this means computation will always eventually run out of gas and then stop. But the danger of a program not stopping is not the only thing to worry about in a completely open and interconnected computation system. The more pertinent issue is: what will a new smart contract do to the total system state? With Turing complete languages, there is one and only one way of finding out and that is to actually go ahead and run everything.

Another way of saying this is that focusing on the Halting Problem in its most literal sense, as in “Will this program stop?” is too narrow a view of the issue. As I explain in the Halting Problem post from my old Tech Tuesday series, any question such as “will this program output the number 42?” or “will this program ever execute line 42 of its code?” is not answerable in the general case of Turing complete languages. For Blockchains an example question is: Will a new smart contract cause any existing smart contract to misbehave? And gas limits do not help with answering that question. In a system where any contract can refer to any other contract that question is not generally answerable for arbitrary Turing complete contracts other than by executing the system.

Some people have proposed formal verification as an answer. I absolutely believe that smart contracts systems should be built in a way that makes formal verification possible. That will help with some problems, such as detecting and preventing certain kinds of bugs that make possible attacks such as the one that drained one third of The DAO. But formal verification does not get around the problem that even trivial questions about how the system will behave as a whole with a new contract added cannot be generally answered.