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:
“The permanence of all books is fixed by no effort friendly or hostile, but by their own specific gravity, or the intrinsic importance of their contents to the constant mind of man.”
—Ralph Waldo Emerson (1803–1882)
“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)