Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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.

share|cite|improve this question
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? – arjafi Aug 5 '12 at 18:35
@ArthurFischer: I am sorry. Is it more clear now? – Numerator Aug 5 '12 at 18:38
Yes, much more clear. Thanks. – arjafi Aug 5 '12 at 18:39

First convince yourself that an obsessive universal machine exists.

Then the following diagonalization argument shows that the set of non-obsessive machines cannot be recursively enumerable. Suppose machine $N$ halts exactly when the input is a non-obsessive Turing machine; then construct the following machine $D$ using standard quine/diagonalization techniques:

machine D is:
   ignore any input;
   construct Y as a description of D itself;
   simulate N on input Y;
   go to a distinguished penultimate state;

The construction of $Y$ is always the same, so it can easily be arranged to happen obsessively, simply by leaving out states that are not needed. Also, the simulation of $N$ can be done using an obsessive universal sub-machine. Thus the obsessiveness of $D$ depends solely on whether the distinguished penultimate state is ever reached. But if $N$ is correct, this will happen exactly when $D$ is not obsessive, so it is obsessive if and only if it is non-obsessive -- a contradiction. So $N$ cannot exist.

The set of obsessive machines cannot be recursively enumerable either. Using the obsessive universal machine, it is easy to translate any machine $P$ into one that is obsessive if and only if $P$ halts on all input. Thus enumerating the obsessive machines would lead to an enumeration of all Turing machines that compute total recursive functions, which is well known to be impossible.

share|cite|improve this answer

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.