# $\{\langle M,q,x\rangle$| $M$ is a Turing machine and $q$ is a state of M and running of $M$ on $w$ visits $q\} \notin R$?

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?

-
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? – Kevin Carlson Aug 1 '12 at 9:16
You mean Turing machine, not turning machine; right? – Martin Sleziak Aug 1 '12 at 9:24
@Martin: Yeah! sorry :) – Joni Aug 1 '12 at 9:30
@KevinCarlson: I hope it is clearer now. – Joni Aug 1 '12 at 9:31
– Carl Mummert Aug 1 '12 at 11:02

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.