Proving decidability

Question

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.

Answer 1

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.

Answer 2

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.