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