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

# 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.