As for "M of N oracles running a public code" mentioned in the article - Orisi.org offers a framework for that.
As for using blockchain directly for contract - there are a few addresses that have funds locked for the first person to find collisions in sha1, sha256 and others: https://bitcointalk.org/index.php?topic=293382.0
Finally, there's (or "there will be") Ethereum which seems best for preparing contracts that require no external inputs. Solving hard problems usually requires no such inputs.