Whitepaper Tuesday 5: Ethereum Isn't Turing Complete, and It Doesn't Matter

This event is cross-posted with IC3 NYC Blockchain Meetup (https://www.meetup.com/IC3-NYC-Blockchain-Meetup/)

The paper is here: http://eprint.iacr.org/2015/675

The talk will start promptly at 7pm and we will not be able to handle late arrivals, sorry. So please get there between 6:30pm and 7:00pm.

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.