I'm trying to construct a recursively enumerable TM for this language. (Useless state: one that is never entered during a computation on any input).

The TM L: Write out all of M's states, generate input in lexicographical order one at a time, and after one is generated, simulate M on the input and mark down which states M has entered. If M enters all states, halt, if M halts without entering all states, generate the next input in lexicographical order and repeat the process. (Keeping the list of entered states between simulations, since once a state is entered for any input, it is not considered useless).

My question is, what happens if M does not halt on input $w_i$ but will halt and in fact enter all states on $w_{i+1}$? Then L will get stuck in an infinite loop on $w_i$ and not realize that M's behavior on $w_{i+1}$ means L should actually accept--thus L will not eventually halt and accept.

Is there a way to deal with this problem or is this TM just not the right way to show this language is recursively enumerable?

  • $\begingroup$ You need to be more careful with your terminology. For instance, by "recursively enumerable TM" you probably mean a semi-decider. $\endgroup$
    – Raphael
    Nov 22, 2017 at 20:38

1 Answer 1


You need dovetailing. This is quite common in such problems.

As you pointed out, we can not simply run $M$ on an input $w$, since that might diverge. To avoid that, we enumerate all the possible pairs $(w,k)$ where $w$ is an input word, and $k$ is a natural. For each such pair, we run $M$ on input $w$ for at most $k$ steps. This will never diverge because $k$ bounds the computation. If $M$ within that bound visits all states, we accept. Otherwise, we try the next pair.

Note that, in order to enumerate all such pairs, we need a computable bijection $(\mathbb N\times \mathbb N) \to \mathbb N$ (or, equivalently, $(\Sigma^*\times \mathbb N) \to \mathbb N$). The existence of such a dovetailing function is one of the standard computability results.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.