I have just added a new opcode to the VM specification which allows long-running computations on the blockchain to a specific limit. These are smart contracts/spending scripts which execute over the span of several blocks and represents a new way of handling the halting problem in blockchains:
Taken from the Technical Roadmap:
OP 0x05 Suspend - Suspends execution of the VM and creates an opaque output with the hash of the current execution state i.e. stack frame + input_stack + output_stack. This output can be respent to resume execution by anyone who includes it in a new transaction along with another input to pay the transaction fees. The VM must be started with special flags to resume the execution of the opaque output which must receive as arguments in the new transaction the following things: the original spending script, and the VM state binary blob.
Also taken from the Technical Roadmap:
With a limit on suspends, nodes can execute the whole chain of transactions and pre-validate them in order to determine if they will all execute whenever they receive a transaction which hits the Suspend opcode. By placing the correct upper bound on suspendable transactions, we can run long computations on the blockchain while also mitigating DDOS vectors in the mempool. The idea is that on the first transaction in a chain of these, the whole computation would be run up to either the number of suspends or the limit on suspends to validate the whole chain. Further transactions wouldn't require validating the whole chain as the VM state proves it was validated via a sequence number included in the vm state binary blob via consensus.
The optimal suspend limit parameter must still be determined by network tests.