Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
Can you have more than one halting state? how do you know which one to use? – Joni Aug 1 '12 at 11:33
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... – Xoff Aug 1 '12 at 11:47
@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). – Raphael Aug 5 '12 at 0:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.