Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.