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

4

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;
   stop.

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.