This is a revised summary of my talk from the November 29, 2012 Theory Lunch. I confess to having made an obnoxious amount of errors during that presentation, for which I apologize to all the listeners. This version is hopefully correct.
There are at least two ways of defining randomness. One is about randomness of distributions of objects: this is the subject of the theory of probability. There is another one, which is about randomness of single objects, and is the subject of algorithmic information theory. Consider the following infinite sequences: Continue reading