Why the web page?- To introduce Algorithmic Information Theory to non-specialists
Algorithmic Information Theory (AIT), or Kolmogorov Complexity as it is usually known to mathematicians, is a potentially useful tool for inquiring into natural systems. However, as AIT has not been widely used outside of mathematics, it is not clear how to apply the approach to natural systems. This web page hopefully will allow those less familiar with the mathematics of Algorithmic Information Theory to access the key ideas. While the web page provides links to relevant articles, (see links in the left hand column) A recent book “Algorithmic Information Theory for physicists and natural scientists” MORE
Key concepts of Algorithmic Information Theory
Any structure or system can be specified by a string of (usually binary) symbols
A Universal Turing Machine (UTM) is a computational device that can simulate any meaningful calculation undertaken on any other computational device. In practice, the typical programmable computer is a UTM. The non quantum universe operating under physical laws is itself a UTM, as is a programmable computer. Even though it is an insignificant part of the universe, in principle, given sufficient time and storage, such a computer can simulate the physical laws that drive one specific state of the universe to another, provided that the computation can recognise the final state and then halt.
A Universal Turing Machine (UTM) is a computational device that can simulate any meaningful calculation undertaken on any other computational device. In practice, the typical programmable computer is a UTM. The non quantum universe operating under physical laws is itself a UTM, as is a programmable computer. Even though it is an insignificant part of the universe, in principle, given sufficient time and storage, such a computer can simulate the physical laws that drive one specific state of the universe to another, provided that the computation can recognise the final state and then halt.
A short description = an ordered system. The core principle of AIT is that those systems that can be specified simply are more ordered. In a nutshell, the length of the shortest algorithm, (i.e. the number of bits in the algorithm) able to specify a system on a standard reference UTM and then halts, defines the system’s algorithmic complexity, the Kolmogorov complexity or “the programme sized complexity”. However, the measure can only be specified to within a constant that captures the fundamental instruction set of the UTM.
Algorithmic Entropy. This is the algorithmic complexity defined above, but the coding set is restricted to self-delimiting coding where, mimicking the natural world, no code can be a prefix of any other. The atoms and molecules in that contain the instructions implementing natural laws behave as real world UTMs. As only entropy differences have physical significance, the algorithmic entropy change in bits, is the real-world programme, simulated on a laboratory computer, that moves a natural configuration from one state to another. This is possible as the simulation constant between the laboratory UTM and the real-world UTM cancels for entropy differences.
Algorithmic entropy and the thermodynamic entropy.
I n contrast to traditional entropies, given an appropriate entropy zero, the algorithmic entropy is the length of the algorithmic to exactly specify a microstate of the system. All microstates in macrostate of the system have same algorithmic entropy. MORE
Landauer’s principle, which applies to any system where temperature has meaning (reference), shows that the cost of removing or transferring a bit in a reversible computation is kBln2T joules. Consequently, for a microstate in the most probable set of states, the number of bits specifying the momentum degrees of freedom, x kBln2 for a microstate, completely aligns with the thermodynamic entropy of the macrostate. Whereas bits specifying stored energy states, like energy are potential thermodynamic entropy only. Bit flows into or out of a system as heat carry kBln2T joules per bit. Provided the bits can be tracked, the flow is reversible, and the total thermodynamic entropy of the system and the environment does not increase. However, when the computational path is not reversible, information is lost, and the total entropy of the system plus the environment increases. MORE
Information measure. The algorithmic entropy is a measure of the information content embodied in the system. This measure is consistent with, but not identical to, Shannon information. The Shannon entropy of a macrostate, the number of bits needed to identify a particular microstate in the macrostate corresponds to the number of bits needed to algorithmically specify a microstate in the most probable set of states.
The universe operating under physical laws is itself a UTM, as is your lap top, even though it is an insignificant part of the universe. In principle, given sufficient time and storage, your lap top can simulate the physical laws that drive one specific state of the universe to another, provided that the computation on the laptop can recognise the final state and then halt. There is an additional obvious proviso that the laptop itself must be excluded from the universe it describes.
Conceptual issues. In the AIT approach, highly ordered structures have low entropy, low algorithmic complexity and low information content. On the other hand, a random string, specifying a random array of constituents, has maximum algorithmic complexity, maximum entropy and maximum information content. Both AIT and Shannon’s information theory assign the most information to the most random strings. The reason is that more bits are required to define or predict an outcome when there is greater uncertainty and, as a consequence, the information is greater. On the other hand, many scientists use an intuitive idea of information which, in contrast to AIT, assigns the greatest information content to the most ordered structures. Similarly, some scientists tend to identify the most complex structures as those that are complicated rather than simple, but which are not random. Any discussion on information or complexity needs to clarify the definitions used and how these might be related to the mathematical definitions of AIT and Shannon. As an example, as used here, a toss of 100 heads in a row is low in information as it can be specified with few bits, on the other hand, the outcome of a random outcome of 100 tosses is high in information.
Conceptual issues. In the AIT approach, highly ordered structures have low entropy, low algorithmic complexity and low information content. On the other hand, a random string, specifying a random array of constituents, has maximum algorithmic complexity, maximum entropy and maximum information content. Both AIT and Shannon’s information theory assign the most information to the most random strings. The reason is that more bits are required to define or predict an outcome when there is greater uncertainty and, as a consequence, the information is greater. On the other hand, many scientists use an intuitive idea of information which, in contrast to AIT, assigns the greatest information content to the most ordered structures. Similarly, some scientists tend to identify the most complex structures as those that are complicated rather than simple, but which are not random. Any discussion on information or complexity needs to clarify the definitions used and how these might be related to the mathematical definitions of AIT and Shannon. As an example, as used here, a toss of 100 heads in a row is low in information as it can be specified with few bits, on the other hand, the outcome of a random outcome of 100 tosses is high in information.