English subtitles

← 21-16 Godel's Incompleteness Theorem

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. You may or may not have heard of Godel's Incomplete Theorem,
  2. but since they are also mentioned in conjunction with the Halting Problem
  3. and undecidability,
  4. it worth saying a few words about them.
  5. Godel's Incompleteness Theorem is named Austrian-born mathematician, Kurt Godel,
  6. are concerned with mathematics,
  7. but are actually closely related to undecidability
  8. and as you might know, any mathematical system starts out
  9. with a set of axioms.
  10. What are axioms?
  11. Axioms are statements which you assume to be true
  12. without having any formal proof of them,
  13. such as if A equals B
  14. and B equals C, then A must also equal C
  15. or you can always draw a line from one point to another point,
  16. no matter where they are.
  17. Those would be axioms.
  18. Now axioms often sound very trivial, like this one here
  19. or the fact that you can always draw a line between 2 points
  20. but for many of them
  21. there are actually scenarios where they are not true.
  22. So axioms are the basis of
  23. any mathematical theorem or proof.
  24. Now what Kurt Godel showed, and it was a shocker at his time
  25. and to many it is still today,
  26. is the following:
  27. So what Kurt Godel showed was that if you had a set of axioms
  28. and they don't contradict each other
  29. and they are listable,
  30. which means you could have an algorithm that lists you all of these axioms,
  31. so either they are finite or
  32. they can even be infinite as long as you have an algorithm
  33. that can produce them all; if this is the case,
  34. then there are some statements
  35. that are true but which you cannot prove
  36. based on these axioms and this is what he meant by incompleteness
  37. how he basically showed that
  38. no matter what foundation you base
  39. a mathematical system on,
  40. as long as that is a consistent foundation,
  41. then you can not prove everything
  42. without adding additional axioms at least.
  43. He also showed, and this is the second Incompleteness Theorem,
  44. which is basically an extension of the first one
  45. that a system of axioms
  46. cannot not demonstrate its own consistency
  47. and what that means is that
  48. very informally,
  49. a mathematical system can not be used to show that
  50. it itself is consistent.
  51. These 2 statements
  52. are in a way very similar to the Halting Problem and Undecidability.
  53. The axioms; you can think of those as programming statements.
  54. So any program or algorithm
  55. is composed of a number of simple instructions
  56. that are then arranged,
  57. and of course there is an infinite number of possible computer programs
  58. that you can write, but they are made up of a fine set of building blocks
  59. and the second Incompleteness Theorem
  60. is of course very similar to undecidability
  61. in the sense that it shows that
  62. you cannot use a system to prove everything about that system,
  63. very loosely speaking,
  64. and the undecidability of the Halting Problem
  65. and all of the other undecidable problems, of course
  66. says that we cannot use algorithms
  67. to calculate everything about algorithms.
  68. I know that from a practical perspective
  69. there's lots of criticism of this,
  70. but truth be told, I just find that super fascinating.