Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. The definition can not be applied equally well to sequences on any finite set of characters, but naively applied in practice. Random sequences are key objects of study in algorithmic information theory.
As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle, there are different notions of randomness. The most common of these is known as Martin-Löf randomness (or 1-randomness), but stronger and weaker forms of randomness also exist. The term "random" used to refer to a sequence without clarification is usually taken to mean "Martin-Löf random" (defined below).
Because infinite sequences of binary digits can be identified with real numbers in the unit interval, random binary sequences are often called random real numbers. Additionally, infinite binary sequences correspond to characteristic functions of sets of natural numbers; therefore those sequences might be seen as sets of natural numbers.
The class of all Martin-Löf random (binary) sequences is denoted by RAND or MLR.
Read more about Algorithmically Random Sequence: History, Three Equivalent Definitions, Interpretations of The Definitions, Properties and Examples of Martin-Löf Random Sequences, Relative Randomness, Stronger Than Martin-Löf Randomness, Weaker Than Martin-Löf Randomness
Famous quotes containing the words random and/or sequence:
“Assemble, first, all casual bits and scraps
That may shake down into a world perhaps;
People this world, by chance created so,
With random persons whom you do not know—”
—Robert Graves (1895–1985)
“Reminiscences, even extensive ones, do not always amount to an autobiography.... For autobiography has to do with time, with sequence and what makes up the continuous flow of life. Here, I am talking of a space, of moments and discontinuities. For even if months and years appear here, it is in the form they have in the moment of recollection. This strange form—it may be called fleeting or eternal—is in neither case the stuff that life is made of.”
—Walter Benjamin (1892–1940)