Everything's there for them to get off the ground, touring complete languages for interoperability between chains have been around for a few years but they're getting a big boost at the mo.
Even ether-ex is semi-centralized, so I don't think the turing complete language is any use. To exchange actual coins on a decentralized exchange rather than tokens representing coins which some centralized entity holds means atomic cross chain transfers, it means paying transaction fees on those blockchains, it means waiting for the usual confirmation times of those blockchains on each trade , possibly even having open wallets for every coin you want to trade. Its difficult to go from the current semi-centralized model to a fully decentralized exchange.
I'm not sure how you get around those problems, but of course that doesn't mean that there isn't a way to do it.