Specific Sequence
Algorithmic information theory (AIT) is the information theory of individual objects, using computer science, and concerns itself with the relationship between computation, information, and randomness.
The information content or complexity of an object can be measured by the length of its shortest description. For instance the string
"0101010101010101010101010101010101010101010101010101010101010101"
has the short description "32 repetitions of '01'", while
"1100100001100001110111101110110011111010010000100101011110010110"
presumably has no simple description other than writing down the string itself.
More formally, the Algorithmic Complexity (AC) of a string x is defined as the length of the shortest program that computes or outputs x, where the program is run on some fixed reference universal computer.
A closely related notion is the probability that a universal computer outputs some string x when fed with a program chosen at random. This Algorithmic "Solomon-off" Probability (AP) is key in addressing the old philosophical problem of induction in a formal way.
The major drawback of AC and AP are their incomputability. Time-bounded "Levin" complexity penalizes a slow program by adding the logarithm of its running time to its length. This leads to computable variants of AC and AP, and Universal "Levin" Search (US) solves all inversion problems in optimal (apart from some unrealistically large multiplicative constant) time.
AC and AP also allow a formal and rigorous definition of randomness of individual strings do not depend on physical or philosophical intuitions about non-determinism or likelihood. Roughly, a string is Algorithmic "Martin-Loef" Random (AR) if it is incompressible in the sense that its algorithmic complexity is equal to its length.
AC, AP, and AR are the core sub-disciplines of AIT, but AIT spawns into many other areas. It serves as the foundation of the Minimum Description Length (MDL) principle, can simplify proofs in computational complexity theory, has been used to define a universal similarity metric between objects, solves the Maxwell daemon problem, and many others.
Read more about this topic: Algorithmic Information Theory
Famous quotes containing the words specific and/or sequence:
“Patriotism is proud of a country’s virtues and eager to correct its deficiencies; it also acknowledges the legitimate patriotism of other countries, with their own specific virtues. The pride of nationalism, however, trumpets its country’s virtues and denies its deficiencies, while it is contemptuous toward the virtues of other countries. It wants to be, and proclaims itself to be, “the greatest,” but greatness is not required of a country; only goodness is.”
—Sydney J. Harris (1917–1986)
“We have defined a story as a narrative of events arranged in their time-sequence. A plot is also a narrative of events, the emphasis falling on causality. “The king died and then the queen died” is a story. “The king died, and then the queen died of grief” is a plot. The time sequence is preserved, but the sense of causality overshadows it.”
—E.M. (Edward Morgan)