In this lesson on diagonalization, functions, and sums, the professor uses a Barber Shop analogy to illustrate the concept of self-reference and the limitations of programs to include themselves in their computation. He goes on to explain how the diagonalization method can be used to show that there are no programs for certain computations, such as finding infinite loops in other programs. The lesson concludes with a subtle and magical proof that highlights the impossibility of a program that accepts all other programs that say no to themselves or infinite loop.
Learn about diagonalization, functions, and a review of sums.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/