F2021 CS 411/811 Lecture 30 (Encoding a TM, Intro to Universal Turing Machines, Diagonalization)

Today we seen how we can encode a Turing Machine, a bit about universal Turing machines, universalism, and then set up things for proving that the diagonalization cannot be recognized by any Turing Machine (we will prove this properly next class) Time Stamps: 0:00 Opening/Reminders 1:55 Encoding Binary Strings as Positive Integers 8:59 Encoding Turing Machines, Intro to the Universal Turing Machine, Encoding Scheme 41:20 Diagonalization Language, Setup for the Next Claim to prove it is not in RE.