L12: Universal Turing Machines; The Halting Problem is Recognizable but not Decidable
Introduction to language ATM, the halting problem; Universal Turing machines show that ATM is recognizable. UTMs define what a computer is in the way that TMs define what algorithms are. Proof that ATM is not decidable by a self-reference argument. This lecture is one of the highlights of the course, showing one of the high points of deduction in the twentieth century.
The podcast Theory of Computation - Fall 2011 is embedded on this page from an open RSS feed. All files, descriptions, artwork and other metadata from the RSS-feed is the property of the podcast owner and not affiliated with or validated by Podplay.