4
$\begingroup$

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:

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.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! FYI, we generally prefer that you ask only one question per post (i.e., pose only one problem per post), as the concern is that someone might answer only one of the three and now the question is treated as "answered". If you have multiple questions, you can ask them separately. In this case listing both $\mathcal{R}$ and $\mathcal{R_S}$ is probably not a big deal in this case as the three questions are so related, assuming you are happy with any answer that solves just one of those two problems, but you might want to ask about $\mathcal{S}$ separately. $\endgroup$ – D.W. Jan 16 '17 at 17:41
  • $\begingroup$ For the first two, see cs.stackexchange.com/q/67259/755 -- I suspect you'll be able to adapt the ideas there to help you solve $\mathcal{R}$. $\endgroup$ – D.W. Jan 16 '17 at 17:44
2
$\begingroup$

$\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.

$\endgroup$
0
$\begingroup$

(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.

$\endgroup$

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.