I'm confused by the use of the expressions "computable problem" and "computable function" in the context of computability theory. Are they refer to the same thing or are there differences?
2
-
$\begingroup$ computable problem --> computer can solve it. computable function --> there exist an algorithm that can solve the function, but not necessary that there exists a computer that can solve the simulated function with the resulted algorithm $\endgroup$– MabadaiMay 31 at 13:15
-
$\begingroup$ @Mabadai I've never seen that; is integer addition really not a computer problem, since there exists integers large enough that no computer can add them? $\endgroup$– prosfilaesMay 31 at 23:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
They're basically the same, in informal usage. They're not necessarily exactly 100% identical.
A computable function is often defined to be a function $f:\mathbb{N}^k \to \mathbb{N}$, or a function $f:\mathbb{N} \to \{0,1\}$, or a function $f:\{0,1\}^* \to \{0,1\}$, that can be computed by some algorithm (e.g., a Turing machine that always halts). These definitions are all basically equivalent, up to encoding of the inputs and outputs.
A decidable language is a set $L \subseteq \{0,1\}^*$ that can be decided ("computed") by some algorithm. It is also sometimes called a recursive language.
These are basically equivalent: for instance, any function $f:\{0,1\}^* \to \{0,1\}$ corresponds to a language $L=\{x \mid f(x)=1\}$, and $f$ is computable iff $L$ is decidable; and conversely the language $L$ corresponds to the function $f(x) = 1$ if $x \in L$, $f(x) = 0$ otherwise.
A "computable problem" is a slightly more informal term, and probably refers to a problem that can be formulated as either a function or a language, and where that function/language is computable/decidable.
Introductory textbooks may choose one of these formalisms and definitions and then work with it in a precise and rigorous and careful way, carefully distinguishing these concepts. Professionals who are experienced in this field might speak a bit more informally and not bother to distinguish between these concepts, as they are after all basically equivalent.
That is my impression about how those terms are normally used, in the absence of any context. Looking at the specific context might influence the interpretation of those terms.
-
$\begingroup$ In some contexts I've seen "decision problem" used specifically for the case $f:\{0,1\}^* \to \{0,1\}$ as opposed to other kinds of problems which can be $f:\{0,1\}^* \to \{0,1\}^*$ (in particular, an "optimisation problem"). $\endgroup$– StefMay 31 at 13:21
-
$\begingroup$ @Stef, yup. Definitions may vary. (Hence the different definitions of what counts as a computable function listed in my answer.) $\endgroup$– D.W. ♦May 31 at 15:44
-
$\begingroup$ @D.W. I also see the expression "computational problem". In light of your answer above, can we define it just as a function? That is, a computational problem is nothing but a function. It might be computable or uncomputable. $\endgroup$– Sanyo MnJun 1 at 14:34
-
1$\begingroup$ @SanyoMn, you can make any definition you want as long as you are clear and it does not conflict with standard practice. Whether that is wise or helpful is another matter. If you want to understand other people's writing, my experience is that the word "problem", as it is commonly used, is an informal term and doesn't necessarily have a precise mathematical definition. It's often a function. If you try to assert that this is the mathematical definition of the word "problem", I don't know whether you might discover some corner cases where that makes it hard to understand others. $\endgroup$– D.W. ♦Jun 1 at 18:45