Prove (non-)recursiveness of a set of Turing Machines defined by behavior

Question

I have a list of problems which I don't know how to prove (non-)recursive (save, I think, for the first), where $\mathcal{M}_n$ is the Turing-Machine with the Gödel-number $n$:

$\mathcal{R}=\left\{n:\mathcal{M}_n\text{ does not move right for any input.}\right\}$

$\mathcal{R}_\mathcal{S}=\left\{n:\mathcal{M}_n\text{ does not move right past the starting position for any input.}\right\}$

$\mathcal{S}=\left\{n:\mathcal{M}_n\text{ does not hang for any input.}\right\}$

Note: The model used within this question is one with a one-side-unbounded tape with the bound being on the left end, thus "hangs" means trying to move off the left end of the tape; the Turing-machine starts right of the input and has three options per step: writing or moving left or right, so no movement is necessary for a step.

I already researched and tried to find solutions of my own, but as Rice's theorem is not applicable, I failed at finding a direct proof of undecidability or proof by reduction (as I cannot think of a way to reduce any known undecidable problem to any of these); research includes:

• http://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW7Sols.pdf
  It seems sensible to perform a breadth-first-search for $\mathcal{R}$, though the presented solution would need to be modified to reflect the different model. This problem seems to be decidable.
• Can an alphabet be extended in a reduction proof? (with sample problem)
  This is quite precisely a question about $\mathcal{S}$, but the proposed reduction reduces the problem to a non-recursive problem, which obviously yields no result at all.

None of my own ideas worked out, thus I have little to show for; I had a vague idea of reducing $\mathcal{S}$ to $\mathcal{R}_\mathcal{S}$ by flipping the input (as well as the movements of the Turing Machine); the main problems are that I have no solution for $\mathcal{S}$ (although I expect it to be non-recursive), and a reduction would need to use an unbounded tape, which may (or may not) break the problem.

Thus, any help (or hint at methodology) would be greatly appreciated.

Answer 1

$\boxed{\mathcal R}$

Idea: If you never move right, you have a regular behaviour. And you can move right iff a "state" in which you can move right is reachable while following this regular behaviour.

Solution:

$\mathcal R$ is decidable

Proof:

Let $\mathcal M$ be a TM with states $Q$ and tape alphabet $\Gamma$. Build the following automaton:

- States: $Q\times (\Gamma \sqcup \{?\})$ where the right component is whatever is on the tape at the current position (we write $?$ if it is whatever was there at the very beginning, and $a$ if we wrote an $a$ there)

- Transitions:
$\hspace{0.5em}$ - $(p, a)\overset{a}{\to}(q,?)$ if the TM can read $a$ while in state $p$ and move left
$\hspace{0.5em}$ - $(p, a)\overset{\varepsilon}{\to}(q,b)$ if the MT can write a $b$ and move to state $q$ if it's in state $p$ and reads an $a$
$\hspace{0.5em}$ - $(p, ?)\overset{\varepsilon}{\to}(p,b)$ (because since we just moved left and never moved right, replacing the letter at that position on the tape by anything wouldn't change the execution until that point).
- The initial states are $(q_i, ?)$ where $q_i$ is an initial state of the TM.

Then in this automaton, a state $(p,a)$ is accessible iff there is a run in the TM so that gets in a state where the TM is in state $p$ and is about to read an $a$ on the tape. So you just have to check if there is an accessible state $(p,a)$ in this automaton so that the TM can read an $a$ while in state $p$ and move right.

---

$\boxed{\mathcal S}$

Idea: Halting for all inputs is "For all input, there is an execution that halts" which is more complicated than the halting problem "Given this input, there is an execution that halts".

Solution:

$\mathcal S$ is undecidable

Proof:

Take a TM $\mathcal M$ and an input $w$. Build a new TM $\mathcal M'$ that erases its input, writes $w$ and then runs $\mathcal M$.

$\mathcal M'$ halts on all inputs
(iff $\mathcal M'$ halts on some input)
iff $\mathcal M$ halts on input $w$

So your problem is undecidable because the halting problem can be reduced to it.

Answer 2

(partial answer)

I think that the complement of the halting problem (on empty tape) reduces to $\mathcal{S}$.

Given a TM $M$, we craft another TM $N$ as follows. Without hanging, we simulate $M$ on the empty tape. Note that, when $M$ moves left and hangs, $N$ does not have to move left and hang (it's only simulating that!), so we can perform the simulation without ever hanging, whatever $M$ does. If $M$ diverges, $N$ diverges without hanging. If instead $M$ halts, then $N$ proceeds in moving left until it hangs.

We have $\#M \not\in HALT \iff \#N \in \mathcal{S}$.

---

For $\mathcal{R}_{S}$, the trick of flipping the tape you mention does not seem to work to me. $\mathcal{S}$ allows an unbounded tape (in one direction), which remains unbounded when flipped, when $\mathcal{R}_{S}$ instead bounds the tape.