4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: the set AlwaysHalt is the set of all (encodings of) total functions. What do you know about this set? $\endgroup$ – Raphael Oct 30 '14 at 13:07
  • $\begingroup$ 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). $\endgroup$ – babou Oct 30 '14 at 13:47
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Lexicographically recursively enumerable" implies "decidable" $\endgroup$ – A.Schulz Nov 2 '14 at 8:40
  • $\begingroup$ @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. $\endgroup$ – InformedA Nov 2 '14 at 18:34
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.