(panoramic photo of Moscow from moscow.photobase.ru)
CCR Logo        

Eighth International Conference on Computability, Complexity and Randomness (CCR 2013)

September 23–27, 2013, Moscow, Russia


Smart Turing machines are slow

Emmanuel Jeandel
In this talk we study the one-tape Turing Machine as a dynamical system (also called in this context a generalized shift), and dynamical invariants related to it, namely its maximum speed (average number of cells read by unit of time) and its entropy (average number of bits needed to code a trajectory). For large classes of dynamical systems (cellular automata, tilings, two-tape Turing machines, piecewise-affine maps...), these numbers are usually not computable, but only computable from above. An exceptional situation arise here for one-tape Turing machines, as the speed and the entropy are actually computable real numbers. This theorem can be seen as a dynamical analogue of the famous theorem by Trakhtenbrot and Hennie that one-tape Turing machines working in linear time recognize only regular languages. We will explain the main arguments in the talk, which involve in particular the rephrasing by Brudno of the entropy as the maximum average Kolmogorov complexity.