# Detecting cycles in off-line Turing machines

Let $M$ be an off-line Turing machine over the input alphabet $\{0,1\}^{*}$, that uses only one working tape in addition to the input tape. Construct a Turing machine $M'$, such that:

• $L(M) = L(M')$
• $M'$ never loops in a bounded space (that is, $M'(w)\uparrow$ may happen only if $M'$ visits infinitely many cells in the computation on $w$)
• for each input word $w$, the number of cells visited by $M'$ in the computation on $w$ is the same as the analogical number for $M$.

$M'$ may use larger working alphabet than $M$.

The only problem in our case is that we don't know a-priory a bound on the location of the head in the work tape. So we adept dynamically - denote by $k$ the leftmost cell reached so far by the head, and count configurations according to $k$. If the head passes the $k$th cell, update $k$ accordingly.
The only remaining problem is counting configurations with only limited space; however, this can be fixed using extended alphabet. Think of every letter in the new alphabet as a pair - one letter from the old alphabet, representing what M sees, and the other letter is in an alphabet big enough so that $k$ digits are enough to represent a number as large as the possible number of configurations.