Fractal Dimension of Space−time Diagrams and the Runtime Complexity of Small Turing Machines
Héctor Zenil · 2013
Complexity measures are designed to capture complex behaviour and to quantify how complex that particular behaviour is. If a certain phenomenon is genuinely complex this means that it does not all of a sudden becomes simple by just translating the phenomenon to a different setting or framework with a different complexity value. It is in this sense that we expect different complexity measures from possibly entirely different fields to be related to each other. In this work we look at small one-way infinite Turing machines (TMs) with two and three states and a binary tape alphabet. For any particular such machine t and any particular input x we consider the space-time diagram of t(x) as the collection of consecutive tape configurations of the computation t(x). We look at the spatial representation s0 of the memory when t starts on input x. Next we look at s1: the spatial representation of the memory after one step in the computation and so forth (see Fig. 1).