Lecture 5: Diagonalization, functions and sums review

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
9048 views | 1 rating
Lesson Summary:

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.

Lesson Description:

Learn about diagonalization, functions, and a review of sums.

More information about this course:
Licensed under Creative Commons Attribution ShareAlike 2.0:

Additional Resources:
Questions answered by this video:
  • 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?
  • Staff Review

    • Currently 4.0/5 Stars.
    This video starts out with an intriguing barber paradox, and uses this as an analogy to a computer program, and then outlines a proof by contradiction to say that such a program cannot exist. Then, functions are discussed in some detail. Next, some more about complexity with Big O and Big Theta are reviewed. Some really interesting and complex sums of series are calculated.