that we can now construct or even foresee. What is more interesting to computer
scientists is that there are questions that can be clearly and simply stated, with an
apparent possibility of an algorithmic solution, but which are known to be
unsolvable by any computer.
Computability and Decidability
In Definition 9.4, we stated that a function f on a certain domain is said to be
computable if there exists a Turing machine that computes the value of f for all
arguments in its domain. A function is uncomputable if no such Turing machine
exists. There may be a Turing machine that can compute f on part of its domain,
but we call the function computable only if there is a Turing machine that
computes the function on the whole of its domain. We see from this that, when
we classify a function as computable or not computable, we must be clear on
what its domain is.
Our concern here will be the somewhat simplified setting where the result of
a computation is a simple “yes” or “no.” In this case, we talk about a problem
being decidable or undecidable. By a problem we will understand a set of
related statements, each of which must be either true or false. For example, we
consider the statement “For a context-free grammar G, the language L (G) is
ambiguous.” For some G this is true, for others it is false, but clearly we must
have one or the other. The problem is to decide whether the statement is true for
any G we are given. Again, there is an underlying domain, the set of all contextfree grammars. We say that a problem is decidable if there exists a Turing
machine that gives the correct answer for every statement in the domain of the
problem.
When we state decidability or undecidability results, we must always know
what the domain is, because this may affect the conclusion. The problem may be
decidable on some domain but not on another. Specifically, a single instance of a
problem is always decidable, since the answer is either true or false. In the first
case, a Turing machine that always answers “true” gives the correct answer,
while in the second case one that always answers “false” is appropriate. This
may seem like a facetious answer, but it emphasizes an important point. The fact
that we do not know what the correct answer is makes no difference; what
matters is that there exists some Turing machine that does give the correct
response.
scientists is that there are questions that can be clearly and simply stated, with an
apparent possibility of an algorithmic solution, but which are known to be
unsolvable by any computer.
Computability and Decidability
In Definition 9.4, we stated that a function f on a certain domain is said to be
computable if there exists a Turing machine that computes the value of f for all
arguments in its domain. A function is uncomputable if no such Turing machine
exists. There may be a Turing machine that can compute f on part of its domain,
but we call the function computable only if there is a Turing machine that
computes the function on the whole of its domain. We see from this that, when
we classify a function as computable or not computable, we must be clear on
what its domain is.
Our concern here will be the somewhat simplified setting where the result of
a computation is a simple “yes” or “no.” In this case, we talk about a problem
being decidable or undecidable. By a problem we will understand a set of
related statements, each of which must be either true or false. For example, we
consider the statement “For a context-free grammar G, the language L (G) is
ambiguous.” For some G this is true, for others it is false, but clearly we must
have one or the other. The problem is to decide whether the statement is true for
any G we are given. Again, there is an underlying domain, the set of all contextfree grammars. We say that a problem is decidable if there exists a Turing
machine that gives the correct answer for every statement in the domain of the
problem.
When we state decidability or undecidability results, we must always know
what the domain is, because this may affect the conclusion. The problem may be
decidable on some domain but not on another. Specifically, a single instance of a
problem is always decidable, since the answer is either true or false. In the first
case, a Turing machine that always answers “true” gives the correct answer,
while in the second case one that always answers “false” is appropriate. This
may seem like a facetious answer, but it emphasizes an important point. The fact
that we do not know what the correct answer is makes no difference; what
matters is that there exists some Turing machine that does give the correct
response.