World's most popular travel blog for travel bloggers.

[Solved]: Is $AlwaysHalt$ recursively enumerable?

, , No Comments
Problem Detail: 

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?

Asked By : Smajl

Answered By : Ran G.

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback