  Complexity measures are designed to capture complex behavior and quantify
*how* complex, according to that measure, that particular behavior is. It can
be expected that different complexity measures from possibly entirely different
fields are related to each other in a non-trivial fashion. Here we study small
Turing machines (TMs) with two symbols, and two and three states. For any
particular such machine $\tau$ and any particular input $x$ we consider what we
call the 'space-time' diagram which is the collection of consecutive tape
configurations of the computation $\tau(x)$. In our setting, we define fractal
dimension of a Turing machine as the limiting fractal dimension of the
corresponding space-time diagram. It turns out that there is a very strong
relation between the fractal dimension of a Turing machine of the
above-specified type and its runtime complexity. In particular, a TM with three
states and two colors runs in at most linear time iff its dimension is 2, and
its dimension is 1 iff it runs in super-polynomial time and it uses polynomial
space. If a TM runs in time $O(x^n)$ we have empirically verified that the
corresponding dimension is $(n+1)/n$, a result that we can only partially
prove. We find the results presented here remarkable because they relate two
completely different complexity measures: the geometrical fractal dimension on
the one side versus the time complexity of a computation on the other side.
