2
$\begingroup$

I have the following question out of an old exam that I'm solving:

Input: a Turing machine and input w Question: Does on running of M on w, at least one of the following things happen           -M stops of w           -M visits the same configuration at least twice 

First I thought that it's clearly in $RE$, it is a recursive enumerable question since we can simulate running of $M$ on $w$ and list the configuration or wait until it stops,

but then I thought to myself:"If it visits the same configuration more than twice, it must be in an infinite loop", because, as I understand, if it reached the same configuration it's gonna copy the same transitions, over and over again, so the problem might be in $R$, it's decidable, since it's the same question as "It stops for $w$ or it doesn't"?

What do you think? Thank you!

  • 0
    In English one may write "M stops." or "Does M stop?", but not "Does M stops?".2012-08-11
  • 0
    Right, sorry :)2012-08-12

2 Answers 2