hine simulator up to n = 10, the smooth line corresponds to a sixth-order fitting and extrapolation polynomial up to n = 20. The inset shows the same data from n = 10 to n = 20 in linear plot with a fourth-order fitting. to execute the full algorithmic computation, and depends on the sizes of the input and of the output. To provide a sense of computation length, let us look at a practical example. Consider, for instance, the following question: "Given two numbers of maximum size n, how many TM transitions are required to perform their multiplication?" We may answer this question by analyzing the operation of squaring integers, as ranging from n = 0 to n = 20, and each time count the number of transitions. The action table corresponds to that of Table 7.6, with n, n for the two input operands. Figure 7.2 shows a plot of the transition counts, as obtained from a TM simulator up to a maximum computation power of n = 10. Polynomial extrapolation makes it possible to evaluate the result up to n = either in logarithmic or linear scales. It is observed from the figure that the number of transitions to compute n2 is subexponential to the integer size n. For n = 0 - 1, the computation requires 12-35 transitions; for n = 10, it requires 11 825 transitions, and for n = 20 the result is evaluated to be 170 851. The fact that the trend is subexponential can be simply explained by the following argument: for sufficiently large n, the TM is essentially found in the states that move the machine towards (state 13) and back to (state 14) the right-hand side of the tape in order to store the 1 symbols defining the result. Each time the trip is one cell longer. With the relation 2 = N(N + 1), where k is the number of cell moves to the result field to write 1 and N = n2 the total number of round-trips, we can evaluate the number of transitions as asymptotically 2 N2 = n4. This is precisely why the linear curve in Fig. 7.2 is very well fitted by a fourth-order Algorithmic entropy and Kolmogorov complexity polynomial. We can thus concl