I have problems with the understanding why a subset of a undecidable language is decidable. We've proved in the lecture that $HALT$$_T$$_M$$=${$<M,w>$|M is a TM and M halts on input w} is undecidable. Can someone give an example of a subset from $HALT$$_T$$_M$ and explain why it is decidable? Is $\Sigma^*$ a valid subset of $HALT$$_T$$_M$?

  • 3
    $\begingroup$ $\Sigma^\ast$ is a superset of $HALT_{TM}$, $\varnothing$ is a subset and decidable. $\endgroup$ – ttnick Sep 3 '19 at 12:14
  • $\begingroup$ It is the 'hard' instances of a language that make a language undecidable. If you're familiar with algorithm analysis, you know that the running time of bubble sort is $O(n^2)$; however, on a fully sorted input, the running time is $n$ steps. The runtime is somewhat analogous to decidability/undecidability. Any instance $<M, w>$ of $HALT_{TM}$ makes a decidable set consisting of one element (because every finite set with elements from $\Sigma^*$ is decidable). However, we are interested in finding an algorithm which would solve the problem for all inputs, not just some subset of inputs. $\endgroup$ – diplodoc Sep 3 '19 at 12:32
  • $\begingroup$ Now I get it. $\emptyset$ and $\epsilon$ are regular and therefore decidable. Thanks. $\endgroup$ – Schleudergang Sep 3 '19 at 13:15
  • $\begingroup$ @BreadCrust $\epsilon$ is a string, not a set. $\endgroup$ – David Richerby Sep 3 '19 at 15:06

An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.


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.