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$.
 A: A standard way to detect cycles in a TM is by counting configurations. For a machine with one input tape and one work tape, a configuration (of M's run on the input x) consists of the current state, the location of the heads in both tapes, and the content of the work tape.
If the location of the heads is known to be bounded, the number of configurations itself is bounded. So if the machine runs more steps than the possible number of configuration, by the pigeonhole principle it entered the same configuration twice, hence it is in a loop, hence we can safely reject.
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.
