2
$\begingroup$

Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting problem to $L_2$.

$L_1$:
On input $w$ the turing machine $M$ never moves it's reading/writing head left. Where $w \in \{0,1\}^*$ and $\langle M \rangle \in \{0,1\}^*$ is the input of $L_1$.

$L_2$:
On input $w$ the turing machine $M$ moves it's reading/writing head in every step (making no neutral move). Where $w \in \{0,1\}^*$ and $\langle M \rangle \in \{0,1\}^*$ is the input of $L_2$.

For $L_1$: I know that a turing machine which can't move left, has no possibility of memorizing it's progress. It only knows the state it's in, so it's similar to a DFA. The difference is, that it reads and/or writes $\{0,1\}^*$ and the blank symbol $\square$. It's also different to a right-moving turing machine because it can do a neutral move. My idea was to construct a $TM$ having two tapes. So that the original tape would scan the input and 'copy' it to the second one. The problem I came across is that I have no possibility of recognizing any loop cycles, so that if $w$ was finished, the $TM$ would never stop writing blank symbols because the tape is infinitely long. Another idea was to construct a $TM$ in which no state has a self-loop. But in this situation I still wouldn't have prevented this infinite writing and I need a $TM$ which halts on every input to prove $L_1$ is decidable.

For $L_2$: I want to reduce the halting problem $H = \{w\#x \mid M_{w}$ halts on $x\}$ to $L_2$ so I can prove that $L_2$ is undecidable. I had the idea of this function $f(<M>,x) \mapsto$ $<M'>\#w\#x$ where I put the input of $H$ into the function and get the input for the $TM$ $M_{{L}_{2}}$ which simulates $L_2$. In addition to that I know that the definition of $M_{{L}_{2}}$ states how it never makes a neutral move but always moves and reads either left or right.

$\endgroup$
0
1
$\begingroup$

For $L_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$. Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by:

  1. The current state.
  2. The tape symbol in the current cell.
  3. The contents of the (infinitely many) tape cells on the right of the head.

There are $|Q|$ choices for 1, $|\Gamma|$ choices for $2$, and $\max\{|w|,1\}$ choices for 3 (since the contents of the tape to the right of the head are always a suffix of $w$ distinct from $w$, followed by infinitely many blank symbols).

To decide $L_1$ it suffices to simulate $T(w)$ for $\eta = |Q| \cdot |\Gamma| \cdot \max\{|w|,1\} + 1$ steps. If $T(w)$ moves its head to the left during the simulation, then reject. Otherwise accept. To see that accepting is the correct choice notice that if $T(w)$ does not terminate within $\eta$ steps, then a state must be repeated at least twice, implying that $T(w)$ is in some loop. This loop can only involve states that appeared at least once during the first $\eta$ steps, showing that $T$'s head will never move to the left.

For $L_2$ see this question.

$\endgroup$
5
  • $\begingroup$ Thank you very much! So what would $T(w)$ do if $w$ was empty? I would've thought it would do the same as you described in case of a loop. Additionally I wondered about the same situation in $L_2$? $\endgroup$
    – st4r5h1p
    Jan 15 at 15:18
  • $\begingroup$ And regarding your comment on $L_2$: "the first one writes $\alpha$, moves its head to the left, and transitions to some new state $q′$." Does that mean in this transition any symbol can be read and replaced by $\alpha$? So that, different than the second transition the tape symbol would be changed? $\endgroup$
    – st4r5h1p
    Jan 15 at 15:28
  • $\begingroup$ $T$ is a generic Turing machine, so what it does when $w$ is empty depends on its description. Anyway the argument in my answer works for all $w \in \Sigma^*$ (including the empty word $\varepsilon$). Also the argument in the linked question continues to work even if $L_2$ is the language of all Turing machines $T$ that move their head in every step when computing $T(\varepsilon)$ (Notice that halting problem is still undecidable even if the input word is fixed). $\endgroup$
    – Steven
    Jan 15 at 15:28
  • $\begingroup$ I meant that you should replace any generic transition that writes (some generic tape symbol) $\alpha$ while changing state to $q$ and keeping the head still, with a pair of transitions. The first transition still writes the same symbol of the original one (i.e., $\alpha$), but it goes in some new state $q'$ and moves its head, say to the left. The second transition resets the head to the previous position by moving it to the right, and changes the state back to $q$. $\endgroup$
    – Steven
    Jan 15 at 15:33
  • $\begingroup$ Thank you so much now I understand! $\endgroup$
    – st4r5h1p
    Jan 15 at 15:34
0
$\begingroup$

A simple solution for $L_1$: Check that for no input symbol there is a move to the left. As the machine will only ever encounter input symbols in it's long march to the right, this is enough.

$\endgroup$
1
  • $\begingroup$ This requires some caution: the machine could replace an input symbol $\alpha$ with some other tape symbol $\beta$ while keeping the head in place. Then there might be a left-movement for $\beta$. Another annoying situation is the one in which there is some input symbol for which the machine could perform a left move, as long as it is in some specific state. This state might or might not be reached (depending on the previous steps) so the mere existence of this transition does not allow us to directly answer "no". $\endgroup$
    – Steven
    Jan 15 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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