You can either go the VM route as Ethereum is doing and in that case gas is how you avoid the halting problem with your Turing completeness or you can go the decidable logic route as Tauchain is doing which means you have no halting problem because you are not Turing complete.
In my opinion the Tauchain decidable logic route is the best approach because it's not a quick hack, it's better for security, it's much more scaleable, but then it takes a lot more effort to do it the right way which is why Ethereum even with mistakes is at least here now.
Digital Asset Holdings recently bought a smart contract company called Elevence which is interesting in that it appears to be going the decidable route with smart contracts. My conclusion is blockchain computation is likely and is also easily scalable depending on the approach. Latency will not be much of an issue if the incentives are set right and there is a supply and demand.
http://www.coindesk.com/digital-asset-acquires-elevence/