7
$\begingroup$

If they are different, what are the typical problems in each that do not fall on the other category? Or are the mutually exclusive or does one completely capture the other?

$\endgroup$
  • 3
    $\begingroup$ Computability is a property of functions, decidability is a property of languages (and problems they represent). I know of no other distinction other than that. $\endgroup$ – saadtaame Sep 15 '12 at 2:11
  • $\begingroup$ Thanks...I'm curious though: What are some typical examples of functions that are not computable? And is a language a finite set of strings? What makes a language be decidable or not? $\endgroup$ – sdfasdgasg Sep 15 '12 at 2:14
  • $\begingroup$ A required property of an algorithm is that of termination, computable functions are defined to capture this property. Therefor, any Turing machine program/function computer that does not halt on all inputs is non-computable. A language is a set of strings over some finite alphabet; the language might be infinite (e.g, the set of binary strings). A language is decidable if there is a Turing machine (actually, I should say Turing machine program) that decides membership in that language (says YES if the input string belongs in the language). $\endgroup$ – saadtaame Sep 15 '12 at 2:24
  • $\begingroup$ W.r.t. your last sentence: Why does the Turing machine care about whether the input string is part of a particular language (it can't read/evaluate it all at once anyway). Isn't all that matters consisting of whether the TM can read the symbol where its head currently is and the TM's current state? $\endgroup$ – sdfasdgasg Sep 15 '12 at 2:51
  • 2
    $\begingroup$ Again, this is pretty basic, mostly definitory stuff. You should spend some more effort on your questions, detailing where your problem lies. $\endgroup$ – Raphael Sep 15 '12 at 13:09
5
$\begingroup$

A function over finite strings is called computable if it can be computed by a program (more formally, a Turing machine).

A set of finite strings is computable if it membership problem in that set (given $x$, is $x \in L$?) can be decided algorithmicaly (more formally using a Turing machine).

They are used for different kind of objects.

The word "computable" can be used for a set. When we say that a set is computable we mean that the set is decidable (which is equivalent to saying that the characteristic function of the set is computable).

It makes no sense to say a function is decidable.

$\endgroup$
  • 1
    $\begingroup$ In the second paragraph, you mean "decidable" instead of "computable", don't you? ("A set of finite strings is decidable ...") Why the "finite" restriction, by the way? $\endgroup$ – chs Dec 30 '15 at 20:18
  • $\begingroup$ @chs When would the TM 'decide', if it were infinite? $\endgroup$ – OJFord Dec 9 '16 at 2:52

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.