Uploaded March 2018 | Updated September 2026, 10 hours ago

---

This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html

Specific topics covered in this lecture: computational universality, the Church-Turing thesis, equivalent computational systems, smallest universal Turing machine, computational universality of toys / nuts-and-bolts / water pipes / billiards, complex gravitational systems, chaos and the butterfly effect, computable puzzles and games, chess, Jeopardy, AlphaGo, self-driving cars and Tesla Model S, uncomputable things: humor / emotions / weather / turbulence / tsunamis / elections / compound pendulums, fractals, algorithmic art, context-sensitive grammars and languages