# Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one:

$AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$

Is $AlwaysHalt$ recursively enumerable?

I would say YES and construct the following TM that accepts this language:

Enumerate all $x \in \{0,1\}^*$ starting with length 1 and then increasing the length in every iteration and try the current $x$ with our TM $M$. We only care about those machines $M$ that halt with all words (we do not care if we do not halt, it would only mean that $R(M)$ is not in our language) so each $x$ will halt eventually. There is only countably many words $x \in \{0,1\}$ so we can do that.

However, I am not sure if this is a correct proof? Can I enumerate all words from and infinite (but countable) language to show that a TM behaves in some way on every single one of them?

• Hint: the set AlwaysHalt is the set of all (encodings of) total functions. What do you know about this set? – Raphael Oct 30 '14 at 13:07
• You can prove (sometimes) that a TM behaves in some way on all strings of a language, but you have to do it globally (possibly using inductive proofs), or at worst with a finite number of cases. Enumeration will not work ... unless you take a lot of testosterone to remain young forever (seen on TV). – babou Oct 30 '14 at 13:47

Consider the language $ALL_{TM}$ (sometimes also called $L_{\Sigma^*}$) $$ALL_{TM}=\{\langle M \rangle: M \text{ is a TM and } L(M)=\Sigma^*\}$$

It is well known that $ALL_{TM}$ is not RE (nor co-RE). See, e.g., this question (and search for other related questions on this site).

From this fact, it is easy to see that AlwaysHalt cannot be RE: a reduction $$ALL_{TM} \le AlwaysHalt$$ is rather trivial.

I can answer a slightly easier version of this question.

Is $AlwaysHalt$ lexicographically recursively enumerable?

Let's say it is. Then we will have an enumeration machine $M_E$ that generates all Turing machines that always halt in some order without repetition.

Let's use this enumeration machine to create another machine $M$ as follows

• On input $<w>$, convert $w$ into an integer $n$
• Use $M_E$ to enumerate and get the n-th generated Turing machine. Let's call this $M_n$
• Run $M_n$ on $w$, when simulation halts, append another symbol into the output.

We can see that $M$ is well defined and always halts because enumeration always succeeds and simulation on an always-halt machine $M_n$ always halts. It is easy to see that $M_E$ generates infinitely many machines because the set of all machines that always halt is not finite. Thus for any number $n$, we can get an always-halt $M_n$ from $M_E$

This machine $M$ is also different from all other machines generated from $M_E$ because of the appending of symbol in step 3. This means $M_E$ does not generate $M$, so $M_E$ does not generate all Turing machines that always halt.

From this we can conclude that $AlwaysHalt$ is not lexicographically recursively enumerable.

This argument can be extended into showing $AlwaysHalt$ is not recursively enumerable by recognizing that eventually for each machine generated by $M_E$ there is eventually a number $n$-th for it. So the machine $M$ is still a always-halt machine and $M$ is still different from all machines generated by $M_E$. So we can conclude that $M_E$ does not generate an always-halt machine. This means $AlwaysHalt$ is not recursively enumerable.

• "Lexicographically recursively enumerable" implies "decidable" – A.Schulz Nov 2 '14 at 8:40
• @A.Schulz That's correct. I believe that because even with repetition $M_E$ will eventually enumerate a given always-halt machine. So the machine $M$ above will still be different from all other always-halt machines enumerated by $M_E$. So $AlwaysHalt$ is also not recursively enumerable. I hoped that other people could help me out on this. Thanks. – InformedA Nov 2 '14 at 18:34

You don't have a single yes/no answer that you can find eventually by enumerating and testing the inputs. So, I think it is not recursively enumerable.

Yes you can enumerate the inputs with a procedure like 0,1,00,01,10... However, you cannot say that this machine accepts this language even if you tested a certain number of inputs.

You can try to reduce the problem to the Halting Problem but this would only indicate that your problem is not decidable.

• You only give intuition, not a proof. Note that you'd have to reduce from the Halting problem, not to. – Raphael Oct 30 '14 at 13:06
• Also, halting problem is recursively enumerable, right? Its just not recursive... – Smajl Oct 30 '14 at 14:28