outward resemblance to the original definition, but each of which satisfy our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money betting on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is a fundamental property of mathematics and not an accident of Martin-Löf's particular model. The thesis that the definition of Martin-Löf randomness "correctly" captures the intuitive notion of randomness has been called the Martin-Löf–Chaitin Thesis; it is somewhat similar to the Church–Turing thesis. Three equivalent definitions Martin-Löf's original definition of a random sequence was in terms of constructive null covers; he defined a sequence to be random if it is not contained in any such cover. Gregory Chaitin, Leonid Levin and Claus-Peter Schnorr proved a characterization in terms of algorithmic complexity: a sequence is random if there is a uniform bound on the compressibility of its initial segments. Schnorr gave a third equivalent definition in terms of martingales. Li and Vitanyi's book An Introduction to Kolmogorov Complexity and Its Applications is the standard introduction to these ideas. Algorithmic complexity (Chaitin 1969, Schnorr 1973, Levin 1973): Algorithmic complexity (also known as (prefix-free) Kolmogorov complexity or program-size complexity) can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence w a natural number K(w) that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output w when run. The complexity is required to be prefix-free: The program (a sequence of 0 and 1) is followed by an infinite string of 0s, and the length of the program (assuming it halts) includes the number of zeroes to the right of the program that the universal Turing machine reads. The additional requirement is needed because we can choose a length such that the length codes information about the substring. Given a natural number c and a sequence w, we say that w is c-incompressible if . An infinite sequence S is Martin-Löf random if and only if there is a constant c such that all of Ss finite prefixes are c-incompressible. Constructive null covers (Martin-Löf 1966):