4
$\begingroup$

Can you please help me understand whether or not the following the problem is recursive, recursively enumerable, or co-recursively enumerable?

A Turing machine $M$ is said to be obsessive if on every input $w$ $M$ goes through all of its states (except possibly the reject and accept states).

Input: (an encoding of) a deterministic Turing machine $M$.

Question: Is $M$ obsessive?

Thank you.

  • 0
    I'm not sure if I understand the problem precisely. First, I would assume that a TM $M$ is _obsessive_ wrt an input $w$ if on input $w$ $M$ runs through all of its states except possibly the rejecting/accepting states. Then would the input be (an encoding of) a TM $M$, and the problem is whether $M$ is obsessive wrt a fixed string $w$? or is the input a TM $M$ along with a string $w$, and the problem is whether $M$ is obsessive wrt $w$? or something else entirely?2012-08-05
  • 0
    @ArthurFischer: I am sorry. Is it more clear now?2012-08-05
  • 0
    Yes, much more clear. Thanks.2012-08-05

1 Answers 1