5
$\begingroup$

In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is what does "undecidable" mean ? I read the "undecidable" applies to problems that have Turing Machines but cannot definitively tell us whether an input is valid or not(i.e. it outputs "yes" for valid inputs, and keep going for others indefinitely such that we will not know when, if ever, it will output anything). Then does "undecidable" applies to problems that can not be represented by Turing Machines at all, also? What is the difference between unsolvable and undecidable ?

EDIT: I was reading my textbook(Introduction to Automata Theory, Hopcroft) and I ran into this: "Remember that showing there is no Turing machine at all for a language is showing something stronger than that the language is undecidable(i.e., that it has no algorithm, or TM that always halts"(pg 388). This seems to imply undecidable problems do not include ones without any TMs. Am I interpreting this correctly ?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ Mathematically "unsolvable" usually means an equation which has no analytical solution for example 0=1+1/(2^x)+1/(3^x) $\endgroup$ – Niklas May 22 '16 at 18:00
  • $\begingroup$ "I understand that if a problem is labeled "decidable", then we can construct a Turing Machine" -- well, no. "there exists" != "we can construct"; see here. $\endgroup$ – Raphael♦ May 25 '16 at 0:21
  • $\begingroup$ @Raphael I guess I didn't know that(thanks for pointing it out). Any ideas on my main question though ? It appears(to me) the textbook is saying undecidable does not include those problems without any Turing machines but answers here indicate otherwise. $\endgroup$ – Jenna Maiz May 25 '16 at 1:42
1
$\begingroup$

Yes, undecidable also applies to problems that cannot be represented by TM at all. The ones where a YES can always be found are a subclass of these called (recursively) enumerable. Unsolvable is a less common term which I know mostly to be used synonymous to undecidable.

So decidable - undecidable but enumerable - non-enumerable is a partition of the class of all problems into three classes, where the middle one is intuitively somthing like the easiest undecidable problems.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ They're usually referred to as recursively enumerable or computably enumerable. $\endgroup$ – jmite May 22 '16 at 16:58
  • $\begingroup$ I was reading my textbook(Introduction to Automata Theory, Hopcroft) and I ran into this: "Remember that showing there is no Turing machine at all for a language is showing something stronger than that the language is undecidable(i.e., that it has no algorithm, or TM that always halts"(pg 388). This seems to imply undecidable problems do not include ones without any TMs. Am I interpreting this correctly ? $\endgroup$ – Jenna Maiz May 24 '16 at 21:15
  • $\begingroup$ Maybe the problem is the exact meaning of "THERE IS a TM" for a problem. Does it mean there is a TM that decides the problem, does it mean there is a TM that always gives a positive answer if there is one. In the latter case it describres the enumerable languages, and not all of them are decidable. Thus showing that there is no machine that enumerates a language is indeed stronger than showing that no machine decides it. $\endgroup$ – Peter Leupold May 25 '16 at 7:18

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.