I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages:

  1. $\emptyset$
  2. $\Sigma^{*}$

I assume for 2, a one-state TM that just automatically accepts would be fine? I don't think it's possible for any input not to halt, or be rejected, so technically the TM would just semi-decide?

However, for 1, I'm not 100% sure what that TM would look like. Would I just have to figure out a way to have at least one input (or, more simply, all inputs), not halt, since none could possibly accept?

Edit: I know such TMs must exist, I'm more so confused as to what they look like.

  • $\begingroup$ Both of your languages are decidable, and so semi-decidable. $\endgroup$ – Yuval Filmus Nov 29 '19 at 22:31
  • $\begingroup$ Yes, but what I'm wondering is how would one go about building a TM that only semi-decides the language, and does not decide. For other languages it can be easy (just ignore the rejecting state, or keep on reading forever). But for something like the universe, how could it not be decidable and only semi-decidable? $\endgroup$ – Lobscurite Nov 29 '19 at 22:44
  • 1
    $\begingroup$ For the empty language, take a Turing machine that enters an infinite loop (regardless of the input). For the complete language, take a Turing machine which immediately halts. $\endgroup$ – Yuval Filmus Nov 29 '19 at 23:09
  • $\begingroup$ @yuval, should be an answer not a comment $\endgroup$ – Ran G. Nov 30 '19 at 13:03
  • $\begingroup$ I don't think Yuval's answer is correct. A TM that immediately halts for the complete language would either be incorrect (if it doesn't accept, than it doesn't actually (semi)decide the language), or deciding (if it immediately accepts, then it decides, and doesn't semi-decide) $\endgroup$ – Lobscurite Nov 30 '19 at 13:52

Your Answer

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

Browse other questions tagged or ask your own question.