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.