Piero Scaruffi(Copyright © 2013 Piero Scaruffi | Legal restrictions )
These are excerpts and elaborations from my book "The Nature of Consciousness"
Algorithmic Information Theory
A fundamental step in bridging the analog and the digital world was taken in 1933 when the Russian engineer Vladimir Kotelnikov discovered the "Nyquist-Shannon" sampling theorem: how to convert continuous signals (e.g. the wave of a sound) into discrete sequences of numbers (e.g. a sequence of zeroes and ones) in such a way that the original signal can be reconstructed without losing fidelity, That was the fundamental mathematical artifice that made the digital revolution possible. No information is lost if a signal is sampled at the proper frequency.
Another Russian mathematician, Andrei Kolmogorov, formulated "Algorithmic Information Theory" ("On Tables of Random Numbers", 1963), a scientific study of the concept of complexity (in 1960 Ray Solomonoff had predated the idea in "A Preliminary Report on a General Theory of Inductive Inference"). Complexity is basically defined as a quantity of information, which means that Algorithmic Information Theory is the discipline that deals with the quantity of information in systems.
The complexity of a system is defined as the shortest possible description of it; or, equivalently, the least number of bits of information necessary to describe the system. It turns out that this means: "the shortest algorithm that can simulate it"; or, equivalently, as the size of the shortest program that computes it.† For example, the complexity of "pi" is "the ratio between a circumference and its diameter".† The emphasis is therefore placed on sequences of symbols that cannot be summarized in any shorter way. Algorithmic Information Theory looks for the shortest possible message that encodes everything there is to know about a system. Objects that contain regularities have a description that is shorter than themselves.
In the terminology of computer science, the Komogorov complexity of a string is the number of bits of the shortest program that can print the string.
Kolmogorov complexity is not computable: there is no program that can computer the Kolmogorov complexity of any arbitrary string.
Algorithmic Information Theory represents an alternative to Probability Theory when it comes to study randomness. Probability Theory cannot define randomness. Probability Theory says nothing about the meaning of a probability: a probability is simply a measure of frequency.† On the other hand, randomness can be easily defined by Kolmogorov: a random system is one that cannot be compressed. A random sequence is one that cannot be compressed any further.
The Argentinean mathematician Gregory†Chaitin†proved that randomness is pervasive. His "Diophantine" equation contains 17,000 variables and a parameter which can take the value of any integer number. By studying it, Chaitin achieved a result as shocking as Goedel's theorem: there is no way to tell whether, for a specific value of the parameter, the equation has a finite or infinite number of solutions. That means that the solutions to some mathematical problems are totally random. Chaitin defined randomness in terms of computability: if it is computable (if there is a program that generates it), a number is not random. Conversely, one can measure the degree of randomness of something by the length of the shortest program (algorithm) that generates it.
Incidentally, every system has a finite complexity because of the Bekenstein†bound. In Quantum Theory the Bekenstein bound (named after the Israeli physicist Jacob Bekenstein) is a direct consequence of Heisenbergís uncertainty principle: there are upper limits on the number of distinct quantum states and on the rate at which changes of state can occur. In other words, the principle of uncertainty indirectly sets an upper limit on the information density of a system, and that upper limit is expressed by the Bekenstein bound.
Physicists seem to be fascinated with the idea of quantifying the complexity of the brain and even the complexity of a human being. The US mathematician Frank Tipler†estimated the storage capacity of the human brain at 10 to the 15th power and the maximum amount of information stored in a human being at 10 to the 45th power (a number with 45 zeros). Freeman Dyson†computed the entropy of a human being at 10 to the 23rd.
Back to the beginning of the chapter "Machine Intelligence" | Back to the index of all chapters