# Turing machines and tape complexity

Are the following statements true and/or false?

There is a total function $g: \mathbb{N} \rightarrow \mathbb{N}$ so that for each Turing machine $M$ and each natural number $t$ we have:

(*) If there is a computation of the Turing machine $M$ for which the tape complexity of the partial computation with $t$ steps is strictly less than $g(t)$, then it is an infinite computation.

Idea: My answer on this statement would be that is is both true and false, because you can inspect different possibilities on what the function $g$ could be. For example if there exists a $t$ for which $g(t) > 1$ then it will be an infinite computation

For each Turing machine $M$ there is a total function $g: \mathbb{N} > \rightarrow \mathbb{N}$ with $g(t) \geq 2$ $\forall t \geq t_0$ (for some natural number $t_0$) such that (*) holds for each $t \geq t_0$.

Idea: I think the last statement will be true, because the tape complexity is always $\geq2$ and the function $g$ is monotonic.

The statement is true. Take $g(t) = \log\log(t)$ or any other function that is significantly smaller than $\log(t)$.
If the TM has $q$ states, and $k$ symbols in the alphabet, then there are at most $q\cdot g(t) \cdot k^{g(t)}$ configurations that use $g(t)$ space. Therefore, in the first $t$ steps the TM saw less than $t$ configurations. This implies that it loops in infinite computation.