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$?
$\begingroup$
$\endgroup$
-
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$ – BreadCrust Sep 3 '19 at 13:15
-
$\begingroup$ @BreadCrust $\epsilon$ is a string, not a set. $\endgroup$ – David Richerby Sep 3 '19 at 15:06
$\begingroup$
$\endgroup$
An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.
