Theory of Computation (CS6160) Lecture 1 (Part 2 of 2), Professor Gabriel Robins

Specific topics covered in this lecture: uncountabiliby of the Boolean functions, uncountabiliby of the reals, simple program that prints out all programs, "size doesn't matter" w.r.t. difficulty of determining halting, arbitrary deep theorems as short codes, proving the uncomputability of the haltiong problem, "Pinocchio's paradox", solving the halting problem with oracles / magic / deities, infinite loops, non-finitely-describable reals, computable numbers are finitely describable, halting problem misnomers