Lecture 5: Diagonalization, functions and sums review

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.

• What is a conundrome in Discrete Math?
• What is Russell's Paradox or the Barber's Paradox?
• If there is a town in which everyone either shaves himself or goes to the barber, does the barber shave himself?
• Why is there no program that finds infinite loops in other programs?
• What is a function, and what does it mean for a function to have one-to-one correspondence?
• What is domain and range for a function?
• What does it mean for a function to be onto?
• Which is larger, x^(log x) or (log x)^x?
• What is the proof that 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2 using induction?
• How can you find and prove the sum of 1^2 + 2^2 + 3^2 + ... + n^2 without induction?
• How do you write and use sigma notation for sums?
• How do you find the sum of squares by finding the sum of consecutive odd integers and manipulating the sum?
• What is the sum of (n - i + 1)(2i - 1) from i = 1 to n?