f algorithmic information theory. Defining algorithmic entropy The concept of information, which has been described extensively in Chapter 3, also evolved beyond Shannon's view, and independently of his classical theory. An alternative definition, which is referred to as algorithmic information, is attributed to G. Chaitin, R. Solomonoff, and A. Kolmogorov. 1 Algorithmic information opened the way to the field of algorithmic information theory (AIT). From AIT's perspective, any source event X is treated as an object variable. The event may consist in any symbol sequence, whether random or deterministic. The focus of AIT is not on the source X, the statistical ensemble of all possible events or symbolic sequences, but on this particular sequence X. See, for instance: http://home.mira.net/~reynella/debate/informat.htm and useful links therein. 7.2 The Turing machine Entering the AIT domain simply requires one to acknowledge the following three basic definitions: (a) The complexity K(x) is defined as the smallest size of a program q(x) necessary to generate the sequence X. (b) Such a program is a finite set of binary instructions with a length of |q(x) bits. (c) The program can be implemented by a Turing machine (TM). The smallest program size, min q(x) = K(x), which is called the complexity of x, is equivalently referred to as algorithmic information content, algorithmic complexity, algorithmic entropy, or Kolmogorov complexity (also called Kolmogorov-Chaitin com- plexity and sometimes noted KC(x) instead).2 The Turing machine, which is named after its inventor, A. Turing, 3 can be viewed as the most elementary and ideal implementation of a computer, and is, as we shall see, of infinite computation power (due to speed, not memory size). To clarify and develop all of the above, we ought first to understand what a Turing machine looks like and how it works; this is addressed in the next section. Then we will investigate Kolmogorov complexity and its properties. Interestingly, I will show that Kolmogorov complexity is