p 106

Brudno’s theorem can be sometimes practical.

 Suppose we wish to compute a trajectory of a discrete time dynamical system defined by a map T. If we encode the trajectory starting from x for a time span of t, its most efficient symbol sequence describing this trajectory has a length of about tK(x, T). To compute a single symbol, we need a certain amount of computational resources, we may interpret K(x, T) as a cost of computing the trajectory per unit time. This interpretation was applied to the 2D Sinai billiard [P. R. Baldwin, “The billiard algorithm and KS entropy,” J. Phys. A  24 , L941 (1991)]. If we regard this dynamical system as a discrete dynamics from one collision to the next, its Kolmogorov-Sinai entropy reads in the small scatterer radius R limit as

 h(R) = −2 logR + constant. + O[R]

[B. A. Friedman, Y. Oono and I. Kubo, Phys. Rev. Lett.  52 , 709 (1984) showed 1/2 < h/ logR ≤ 2, and computationally the upper bound was shown to be the answer. Later, this was proved in N. I. Chernov, Func. Anal. Appl.  25 , 204 (1991)].

 Brudno’s theorem tells us that there must be an algorithm whose CPU time should be proportional to −logR. Indeed, Baldwin gave such an algorithm in the above paper. 

 Generally speaking, if the required CPU time and the Kolmogorov-Sinai entropy do not exhibit a similar parameter dependence, better algorithms should be explored.