## ← 02-05 Kolmogorov Complexity Solution

• 1 Follower
• 54 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=YgnPUb2uLFg" data-team="udacity"></div> ``` 1 Language

• English [en]

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.
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,