0
$\begingroup$

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?

$\endgroup$
1
  • $\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

0
$\begingroup$

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.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.