A complete, exact description of an object is one from which all properties of the object can be reconstructed. If the object is information, e.g. a text, a data structure, an image or sound file etc., this means that the original data structure can be reconstructed from the description.
If the description is shorter than what is described, the described data must necessarily contain some regularity, order or repetition. The description is then a compression of the original data. The compression is possible because of the order. A completely unordered, random data object cannot be compressed.
If you have some channel through which you receive the information (e.g. a music stream from the internet), you might have a complete description of the signal coming through that channel (e.g. you know every detail of the music coming through the channel). You can then use this description to predict the signal. The knowledge or description may then be viewed as a formal theory about the signal that can be used to derive predictions about it.
Now, if the signal is longer than the description (the knowledge you have about it), it must contain some regularity or redundancy because if the description is exact and complete (i.e. the original information can be recovered from it) and it is shorter than the original information, it is a compressed form of that information. But if the original information can be compressed, it must contain some order.
So for any signal channel for which there is a finite complete description of its content, if the length of observation (say m bytes) exceeds the length of the description (say n bytes), the signal must contain some kind of order because the data can be compressed (into the description).
This means that the signal cannot exhaust the bandwidth of the channel completely if its length exceeds the length of the description. If there is order, there must be some unused bandwidth. You could compress the signal into a shorter signal andthus free some time slot through which additional information can be sent. So the signal described by the description cannot use up the channel’s bandwidth completely.
An unordered signal, on the other hand, would be a random signal; it would be something like what is called “white noise”. It would not be compressible. There can never be a complete description of such a signal because any description valid for a limited stretch of the signal can be broken by additional observation .
A signal containing order, on the other hand, has a structure. It is not completely random. A channel that contains an ordered signal would not exhaust the channel completely. There would be room for additional signals. But these would not be covered by the description of the original signal.
We can describe our interface with reality (through our senses) as a channel carrying a signal. If we have limited knowledge of reality, i.e. a limited and finite description of it, that knowledge could never exhaust the bandwidth of the channel. It would only describe a subset of reality (except reality had a simple, ordered structure). So whatever knowledge we have, there is room for additional, new or surprising experiences.
If our cognitive system was an algorithm, i.e. a finite set of rules about how to interact with the environment, this algorithm could be viewed as a finite description of reality. It could then only cover part of the bandwidth of our interface with reality. So there could be additional signals (i.e. things happening in reality) not covered by this algorithm. We would then be limited in our ability to understand reality. We could understand reality only if it was very well behaved and regular, but that is not what we are finding.
If, on the other hand, our ability to understand reality (i.e. to discover structures or order in the signal) is unlimited, our cognition cannot be an algorithm. It would instead have to be extensible, so the description of the world could be augmented by new parts. Our cognition would have to be able to change beyond the limits of any single description (or algorithm or formal theory).
If there is a complete description of cognition, i.e. cognition is understandable completely, then cognition would have to be limited and we could only understand an ordered subset of the world. If cognition is universal, there cannot be a complete description of it, i.e. of ourselves. We must be creative in order for our cognition to be universal.
(The picture is from http://upload.wikimedia.org/wikipedia/commons/4/4f/Triangle-td_and_fd.png. It shows a triangle-shaped signal and the spectrum of that signal, i.e. a plot of the frequencies and amplitudes from which the signal could be reconstructed by adding them. The gaps in the spectrum clearly show that the signal described by it is an ordered structure. The bandwidth is not exhausted, additional frequencies could be squeezed in between. The signal could be described by a simple short text or a small programm.)