Abstract

This chapter introduces the definitions of the notion of a random sequence using the three main ideas described that have dominated algorithmic randomness. There are three key approaches for defining randomness in sequences: unpredictability, typicality, and incompressibility. A notion is set up notation for strings and sequences, the Cantor Space, which forms the basic framework for carrying out further discussions, and contains a brief and informal introduction to Lebesgue measure on the unit interval and the Cantor space, which one treats as equivalent. Discussion of mathematical randomness defines a series of classical stochastic or frequency properties in an effort to distill out randomness. This chapter further forms the core material on algorithmic randomness: Von Mises randomness, Martin-Lof randomness, Kolmogorov complexity and randomness of finite strings, application to Godel incompleteness, and Schnorr's theorem. It forms an overview of other forms of related randomness notions that have been studied and indicates the current state of affairs.