1
$\begingroup$

$L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$
$L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} \}$

Consider the two languages above. I want to know which ones are decidable.

I know that $L_1$ is decidable, because $M$ has only a finite amount of possible configurations with the input string $w$, so we can create a Turing Machine (TM) for to check 1 step past the number of combinations and decide.

However, for $L_2$, can we do that? I feel like $L_2$ is undecidable, because we can there seems to be no limit to the possible configurations.

Improve this question
$\endgroup$
2
  • $\begingroup$ If $M$ cannot know whether it is on the end of the input string when it is on the end of the input string, then it has to move past the input string before it realizes the input string has ended, which means $M$ has to stay put all the time to avoid moving its head past any input string. That is, I believe, not the intention of this question. So, I would like to consider the model for the Turing machines used here will have the end of the input string on the tape marked by a special marker. $\endgroup$
    – John L.
    May 19, 2020 at 16:08
  • $\begingroup$ In fact, even if $M$ stays put all the time, it is suspected of being outside of the input string if the input string is empty. Here is a clearer way to define $L_2$. $L_2$ is the collection of Turing machines that never move their heads more than 1 cell away from any input string. (My answer becomes more rigorous against this new definition of $L_2$. $\endgroup$
    – John L.
    May 19, 2020 at 16:10

1 Answer 1

Reset to default
1
$\begingroup$

The halting problem, $\mathsf{HALT}$ reduces to $\overline{L_2}$.

Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, simulates $T$ on input $w$ for $n$ steps and then stops except that if $T$ ever halts before $n$ steps, $N$ will move its head to the right forever.

There is a gap in the above reduction. When $N$ simulates $T$ on $w$ for $n$ steps, it may move out of the input when it moves left (we assume that input is put to the right of the origin, the initial position of $N$'s head, inclusively). This gap can be resolved by the classic trick of "translating the tape". When the simulation is about the move to the left of origin, let $N$ translate the current of the tape one cell to the right. Then $N$ goes to the origin, as if it were the cell to the left of the origin. In this way, we will make sure $N$ will never move out of the input string as long as the simulated $T$ on $w$ does not halt. (To enable $N$ to recognize the origin, it should always mark the origin with a "compound" symbol that also tells its original symbol. For example, if the original symbol at the origin is $A$, $N$ should change it to $A_o$, a symbol that is not $A$ but points to $A$. "Compound" symbols are also used when $N$ translates the content of the tape.)

Since $\mathsf{HALT}$ is not decidable, $\overline{L_2}$ is not decidable. So, $L_2$ is not decidable.

Improve this answer
$\endgroup$
7
  • $\begingroup$ "the current of the tape" should have been "the content of the tape". $\endgroup$
    – John L.
    May 19, 2020 at 16:14
  • $\begingroup$ I should have emphasized your intuition, "$L_2$ is undecidable, because we can have input strings of longer and longer length." Unbounded situations will lead to undecidability in general. $\endgroup$
    – John L.
    May 19, 2020 at 16:18
  • $\begingroup$ I should mention that during the simulation, $N$ must keep track of the end of what have been read so far. Also when translating the tape, the unread part of the input string should be encoded as part of the symbols on the tape. Anyway, the idea is to simulate $T$ on $w$ only on the first $n$ cells, with the powers from more kinds of symbols available to use. $\endgroup$
    – John L.
    May 19, 2020 at 16:38
  • $\begingroup$ I fail to see how HALT appears in the reduction. Aren't you reducing from the language of Turing Machines that halt in fewer than |w| steps, which is not exactly HALT? I obviously believe that such language is undecidable as well, but it's similar enough to the language in the question that I'd expect a proof of its undecidability. $\endgroup$
    – Bernardo Subercaseaux
    May 19, 2020 at 19:07
  • $\begingroup$ @bernardosubercaseaux "Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, ..." $n$ means any natural number. $n$ has nothing to do with $w$. In particular, $n$ can be larger than $|w|$. $\endgroup$
    – John L.
    May 19, 2020 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.