final output of the program is the bit sequence written on the tape, which is left at the point where the machine halted. To illustrate how the TM works, consider next a few program examples including the basic operations of addition, subtraction, multiplication, and division. Example 7.1 This is a TM program that creates the 5-bit sequence 11011 out of an initially blank tape with equivalent sequence 00000 Table 7.1 shows the action table instructions and Table 7.2 shows the step-by-step implementation on the tape. It is assumed that the first initial state is S1 and that the head is located at the leftmost cell, as underlined. Table 7.2 illustrates, each of the computation steps is characterized by a left-to-right tape move (or equivalently, right-to-left head move, as viewed from the tape) with a possible change in the cell contents. It is seen that the machine halts at step 6, because there is no instruction in the action table concerning an input state S1 with a cell reading of 1. Algorithmic entropy and Kolmogorov complexity Table 7.3 Example of action table for Turing machine defining the addition of two numbers in the unary system. Input Change of cell Output state contents state Example 7.2 This is a TM program that adds two integers. Such an operation requires one to use the unary system. In the unary system, the only symbol is 1 (for instance) and an integer number n is represented by a string of n consecutive 1s. The decimal numbers 3 and 7 are, thus, represented in unary as 111 and 1111111, respectively. Adding unary numbers is just a matter of concatenating the two strings, namely, 3 + 7 = 111 + 1111111 = 1111111111 = 10. Because we are manipulating two different numbers, we need an extra blank symbol, 0, to use as a delimiter to show where each of the numbers ends. Thus, the two numbers, 2 and 3, must be noted as the unary string 1101110. We use this string as the TM input tape. The action table and the step-by-step implementation of its instructions are shown in Table 7.3 and 7.4, respectively. It