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?

  • 1
    Sorry, Joni, there are several unclear spots in here-do you mean the $x$ in your first formalization to be the same as the $w$? You're right that you can't identify a Turing machine in a loop by a repeated configuration, but I can't follow your last paragraph. Do you mind describing more carefully your definition for the acceptance problem, and exactly how you're doing a reduction?2012-08-01
  • 1
    You mean [Turing machine](http://en.wikipedia.org/wiki/Turing_machine), not turning machine; right?2012-08-01
  • 0
    @Martin: Yeah! sorry :)2012-08-01
  • 0
    @KevinCarlson: I hope it is clearer now.2012-08-01
  • 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
    Can you have more than one halting state? how do you know which one to use?2012-08-01
  • 0
    yes, but usually we only consider one. In the halting problem, we usually consider only one, but the result stay true if you have several ones, and you ask for only one, or for any subsets of them...2012-08-01
  • 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