Algorithmic randomness is the property of an infinite binary sequence that passes every effective test for randomness with respect to fair coin tossing. The definition using the tests below is also called Martin-Löf randomness (Martin-Löf 1966).
A test consists of sets 
, 
, ... of infinite binary sequences. A single algorithm
enumerates ordered pairs 
, where 
is a finite binary string,
and 
is the union of the sets of all
infinite sequences starting
with a string 
enumerated for 
. The test must satisfy
 |
for every positive integer 
, where 
is the probability obtained
from independent fair coin
tossing. In particular, the set of sequences
starting with a fixed 
-bit string
has probability 
.
An infinite binary sequence 
is algorithmically random iff
 |
for every such test. No computable infinite sequence is algorithmically random. For a given computable sequence,
an algorithm can enumerate its first 
bits for each 
, producing a test that contains the sequence
in every 
.
The binary expansion of a Chaitin constant is algorithmically random (Chaitin 1975, pp. 337-338).
