Rate of tape growth

The rate of tape growth of a given Turing machine (also called the order of the Turing machine), written $G_T$, is a function which inputs a positive integer $n$ and outputs the number of cells which have been read by the head at least once up to the first $n$ transitions.

Rates of tape growths are usually denoted using big O notation, as finding closed form generating functions for $G_T(n)$ can be difficult and is not always of interest.

The fastest possible order of a Turing Machine is exactly the identity function $G_T(n)=n$. It has been conjectured that the fastest possible sublinear order is $O\left(\frac{n}{\log n}\right)$.

Another tape growth function, $\gamma$, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after $n$ transitions. This function is used infrequently. $\gamma (n)$ is always bound from above by $G_T(n)$.