This is an archived page from the Fall 2019 version of the course. For the latest version, see https://uvatoc.github.io.

Class 15: Universality and Uncomputability

Slides
Video

TCS Chapter 8: Universaility and Uncomputability

Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. 1936. (bug fix) (You missed your chance to by an original printing for GBP 30,000.)

According to Scott Aaronson, Dori-Mic and the Universal Machine! A Tragicomic Tale of Combinatorics and Computability for Curious Children of All Ages is “The BEST babies’ book about computational universality I’ve read.". I have free copies available for anyone who needs a holiday present for a young sibling/cousin/nibling/other person who is behind in her theoretical computer science education and needs a holiday present for any cs3102 students who ask.