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{\bigg (}{\frac {n}{\log n}}{\bigg )}$.

Another tape growth function, the rate of strict tape growth $\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 bounded from above by $G_{T}(n)$.