Ethereum Isn't Turing Complete, and It Doesn't Matter Anyway





The interactive transcript could not be loaded.


Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Aug 7, 2016

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.


When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to

Loading playlists...