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?
Asked By : sdfasdgasg
Answered By : Kaveh
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3555
0 comments:
Post a Comment
Let us know your responses and feedback