4
$\begingroup$

I'm trying to find where does the language $\{\langle M,q,x\rangle$| $M$ is a Turingmachine and $q$ is a state of M and running of $M$ on $w$ passes on $q\}$ belong? whether it's $R,RE$ or none of the above.

At first, I thought it is decidable, since if it halts I can go through the states that it visited, and if it is not stopping I can tell from detecting a specific configuration twice that it's in loop, but it is correct for Linear bounded automate and not for a infinite stripe machine (Am I correct?).

Then I wanted to prove that it's not in $R$.I want to make a reduction from the acceptance problem: Can I do the following? given $(\langle M\rangle,x)$ I give the same $(\langle M\rangle,x)$ and a $q$ that would be the accepting state of $M$. if it doesn't have any, it would be a new isolated state, so I get that if M accepts x it visits $q$, otherwise it's not.

The recursion: $f(\langle M \rangle, x)= (\langle M' \rangle, x',q')$

given $(\langle M\rangle,x)$ I construct the new $M'$ as the following:

If $M$ accepts $x$, $M'$ would be a copy of $M$, $x'=x$ and $q'=q_a$ where $q_a$ is the accepting state from original $M$, if it's not I copy $M=M'$ , $x=x'$ and $q'$ would be a new isolated state where no running reaches. basically I ignore the input of the new $M'$ and use it only with given $x$.

Am I correct?

  • 2
    See http://cs.stackexchange.com/questions/636/a-question-relating-to-a-turing-machine-with-a-useless-state2012-08-01

1 Answers 1

4

It's not recursive, because if you can decide if $\langle M,q,x\rangle$ is in your language, then you can decide if the machine $M$ stop on entry $x$, by testing if $\langle M,h,x\rangle$ is in your language ($h$ is the halting state). So you can decide the halting problem. And this problem is uncomputable, so is your language.

But it's obviously RE, as you can simulate $M$ on $x$ and say "yes" if you use the state $q$ after some steps of computation.

  • 0
    @Joni: You can easily construct a machine with only one halting state (which is never left) from any other (and use that one for the reduction).2012-08-05