Ethereum Isn’t Turing Complete and it Doesn’t Matter Anyway

Professor Andrew Miller, IC3 Associate Director, Department of Computer Science, University of Illinois, Urbana Champaign will talk about “Hawk” — the blockchain confidentiality protocol he pioneered, smart contract programming in general, and relevance of the concept of Turing completeness, which is often misinterpreted.

Abstract: Turing completeness is a red herring. It’s commonly misused as a catch-all buzzword to mean “expressive”, or “universal.”

In computer science theory, Turing completeness is indeed universal for “computable functions”, but cryptocurrencies are about much more than computable functions — — they require interaction and distributed communication, for example. Turing completeness doesn’t say much about these settings.

In this talk, I’ll explain exactly what Turing completeness means and doesn’t mean. Spoiler: Ethereum isn’t Turing complete anyway!

People often think “loops” are necessary and sufficient to be universal. Actually, even a system without loops, like Hawk, based on “circuit families”, can represent any computable function as well.

I’ll also give examples of Turing-complete cryptocurrency designs that are useless.

Finally, I’ll explain why the halting problem is not a good excuse to ignore formal methods for validating smart contracts.