Theory of Computation (CS3102), Lecture 07, Professor Gabriel Robins, Spring 2018

Specific topics covered in this lecture: Alan Turing, countability of algorithms, uncountability of functions, what is a function, algorithms / code vs. functions, non-computability, the halting problem, short but difficult instances of halting problem, embedding arbitrary mathematical conjectures as halting problem instances, the "3x+1" problem, Turing's proof of the non-computability of halting problem, algorithms vs. "magic"