0
$\begingroup$

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$?

$\endgroup$
4
  • 3
    $\begingroup$ $\Sigma^\ast$ is a superset of $HALT_{TM}$, $\varnothing$ is a subset and decidable. $\endgroup$
    – ttnick
    Sep 3, 2019 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$
    – diplodocus
    Sep 3, 2019 at 12:32
  • $\begingroup$ Now I get it. $\emptyset$ and $\epsilon$ are regular and therefore decidable. Thanks. $\endgroup$ Sep 3, 2019 at 13:15
  • $\begingroup$ @BreadCrust $\epsilon$ is a string, not a set. $\endgroup$ Sep 3, 2019 at 15:06

1 Answer 1

1
$\begingroup$

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

$\endgroup$

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.