Kolmogorov Complexity

Readings:

Skim the Wikipedia page on Kolmogorov Complexity: http://en.wikipedia.org/wiki/Kolmogorov_complexity

Also, read this article, Complexity and Intelligence by Eliezer Yudkowsky, or at least enough of it to answer the reading questions: http://lesswrong.com/lw/vh/complexity_and_intelligence/

(Use the links within the article to clarify points if you need to - but be careful not to get lost on LessWrong.com, at least not until you have a couple of hours of free time)

Reading Questions:

1. How is complexity defined in a mathematical sense (in words, don't just write a formula)?

2. Why is a subset of the Mandelbrot set more complex than the entire set?

3. What is the relationship between the randomness and the complexity of a pattern?

Lecture Notes:

(see attached)

Class Activities:

How can we prove that Kolmogorov Complexity is incomputable?

There are two proofs which are outlined in the lecture notes, but see if you can figure them out on your own first.

Homework:

Let's say that the function KP is the Kolmogorov Complexity under the Turing machine which emulates Python. See if you can approximate the KP of the following patterns:

1. The finite binary string "1111111111111111"

2. The infinite binary string "10110111011110111110....."

3. The lyrics to the song "99 bottles of beer on the wall"

4. The lyrics to the song "Stairway to Heaven" by Led Zeppelin

5. The first thousand digits of pi (since you can't actually output 1000 digits without writing a LOT of code, see if you can write a function that calculates this, even if it doesn't display it).

Quiz:

1. Which is more complex: a 30,000-character computer science research paper, or 30,000 entirely random characters? Why?

2. Which is more complex: a string containing the first thousand decimal digits of the square root of two, or a string containing the second thousand? Why?

3. Sketch a proof that Kolmogorov Complexity is incomputable.