Is language {M | M halts and print "Hello World"} recursively enumerable? I'm not sure my proof is correct. Let universal Turing machine U start another Turing machine M2 that reads result of work of given Turing machine M1, which halts on "Hello World" and goes to infinite loop otherwise. Then M2(M1) halts if and only if M1 prints hello "Hello World".

  • 2
    $\begingroup$ The language is recursively enumerable, but your argument does nothing to show this. $\endgroup$
    – Arno
    Oct 1, 2019 at 14:00

1 Answer 1


Enumerate all turning machines $M_1, M_2, \dots, $ and simulate them in a dovetail fashion, i.e., proceed in rounds:

  • In the first round simulate $M_1$ for $1$ step;
  • In the second round simulate $M_1$ and $M_2$ for one (more) step each;
  • In the third round simulate $M_1$, $M_2$ and $M_3$ for one (more) step each;
  • ...

In general, at the $i$-th round you perform one additional step for all turning machines in $\{ M_1, \dots, M_i \}$ that have not yet halted. Whenever a Turing machine $M$ halts, check if its output is "Hello World" and, if so, return $M$.


Your Answer

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

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