English subtitles

← 02-05 Kolmogorov Complexity Solution

Get Embed Code
1 Language

Showing Revision 1 created 04/27/2012 by Amara Bot.

  1. The answer is that it's theoretically impossible
  2. to compute this for an arbitrary sequence.
  3. The first answer is not correct.
  4. If S is truly random, this would be correct.
  5. But if S is not truly random, there might be some shorter way to compute it.
  6. So this gives the maximum value of the Kolmogorov Complexity
  7. of sequence length S.
  8. And an example of such a program would just be this Python program,
  9. that would be the program "print" + S.
  10. That would print out the sequence S.
  11. It's length would be the length of S plus the 5 characters for the print
  12. plus 1 for the space.
  13. But that doesn't prove that there isn't a shorter program that can produce S.
  14. The trick in the second answer is this part.
  15. This assumes that we can execute P to completion.
  16. In order to do that, we would need to solve the halting problem.
  17. We would need to know that P will either never finish
  18. or know how long to wait to keep running P.
  19. So we can't actually do this step.
  20. This might run forever; this loop may never finish.
  21. So we would never learn the result. So that's why this doesn't work.
  22. This is not enough to prove that it's impossible,
  23. because maybe there's some other way to do it.
  24. And I'm not going to go through
  25. how we actually prove that the Kolmogorov Complexity is uncomputable,
  26. but I'm going to show you a paradox that will give you a little bit of an idea
  27. why that is.
  28. The paradox is known as the Berry Paradox.
  29. What the paradox asks is,
  30. "What is the smallest natural number--"
  31. and by that I mean the set of numbers 1, 2, & 3--
  32. sometimes we'll design it starting from 0--
  33. the paradox would work just as well either way--
  34. "that cannot be described in eleven words?"
  35. So this seems like a reasonable question.
  36. We can define the set of numbers that cannot be described in eleven words.
  37. It seems like a perfectly reasonable description of a set.
  38. It's also a case that any set of natural numbers
  39. has the smallest element.
  40. The numbers are well-ordered, so whatever that set is,
  41. there must be some smallest number.
  42. So that means there should be an answer to this question--
  43. that there is a smallest number that cannot be described in eleven words.
  44. And I'm going to describe it for you.
  45. Here's my description.
  46. And my description has 1-2-3-10-11 words.
  47. So I just described the smallest natural number
  48. that cannot be described in eleven words,
  49. but I've described it in eleven words.
  50. So that suggests that no such number exists,
  51. but that contradicts the properties we had before.
  52. That's why this is a paradox.
  53. This is certainly not a proof that the Kolmogorov Complexity is undecidable,
  54. But it should give you some sense of how we might prove that.