Infinite Complexity (with some maths -only really basic, i promise)
Suppose we have a set of counting numbers (1, 2, 3...). If we have any finite set then the set can easily be described by listing all the elements. For many infinite sets, descriptions can easily be provided.
For example:
1,3,5,7... are the old numbers
1,4,9,16,25 are the square numbers.
The question is:
Does there exist any infinite set that cannot be finitely described?
The answer is yes. First we have to define what we mean by description. Well not really. We will just assume that it is a string, which of course means it can be converted into a stream of 1s and 0s (binary). This can of course be converted into a single integer. For those with a greater mathematical knowlege, Cantor's Diagonalisation will immediately realise that such a series exists as there is no bijection between desciptions (integers) and infinite sets. This isn't too hard to understand and you might want to read it afterwards.
However, this note will describe an alternate method. Suppose we have a gambler. He is playing a flip the coin game. There is clearly no way he can have a non-zero probability of winning every time! He wishes to know when it will be heads, which can be represented as an infinite set of the counting numbers, where n is in the set if and only if the nth throw is heads. Now suppose there was a finite description for every infinite sequence. If we could generate descriptions, giving each a non-zero probability then our gambler would have a non-zero probability of guessing when it was heads and hence always win.
But the thing is, we can. Distribute the first half of probability to 1, the next 1/4 to 2, the next 1/8 to 3... Clearly all integers (which represent descriptions) have non-zero probability which is a contradition. So obviously, not all infinite sequences can be described. This has a number of consequences which I will discuss in a future note.
