Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

algorithmic complexity





A measure of complexity that has been developed by Gregory Chaitin and others and is based on Claude Shannon's information theory and earlier work by the Russian mathematicians Andrei Kolmogorov and Ray Solomonoff. Algorithmic complexity quantifies how complex a system is in terms of the length of the shortest computer program, or set of algorithms, need to completely describe the system. In other words, it is how small a model of a given system is necessary and sufficient to capture the essential patterns of that system. Algorithmic complexity has to do with the mixture of repetition and innovation in a complex system. At one extreme, a highly regular system can be described by a very short program or algorithm. For example, the bit string 01010101010101... follows from just three commands: print a zero, print a one, and repeat the last two commands indefinitely. The complexity of such a system is very low. At the other extreme, if system is totally random its algorithmic complexity is very high since the random patterns can't be condensed into a smaller set of algorithms: the program is effectively as large as the system itself.


Related entry

   • compressible


Related category

   • COMPUTERS, ARTIFICIAL INTELLIGENCE, AND CYBERNETICS