patternModerate
Are "computable problem" and "computable function" the same thing?
Viewed 0 times
problemsamethecomputablearefunctionandthing
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#160407, answer score: 17
Revisions (0)
No revisions yet.