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?

  • 4
    $\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$
    – mrk
    Sep 15, 2012 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, 2012 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$
    – mrk
    Sep 15, 2012 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, 2012 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, 2012 at 13:09

1 Answer 1


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.

  • 3
    $\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, 2015 at 20:18
  • $\begingroup$ @chs When would the TM 'decide', if it were infinite? $\endgroup$
    – OJFord
    Dec 9, 2016 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.