772
Modeling Arithmetic, Computation, and Languages
Definition DECision ProBLEM
A decision problem asks if an algorithm exists to decide whether individual
statements from some large class of statements are true.
The solution to a decision problem answers the question of whether an
algorithm exists. A positive solution consists of proving that an algorithm exists, and it is generally given by actually producing an algorithm that works. A
negative solution consists of proving that no algorithm exists. Note that this
statement is much stronger than simply saying that a lot of people have tried
but no one has come up with an algorithm—this might simply mean that the
algorithm is hard. It must be shown that it is impossible for anyone ever to come
up with an algorithm. When a negative solution to a decision problem is found,
the problem is said to be unsolvable, uncomputable, or undecidable. This terminology can be confusing because the decision problem itself—the question
of whether an algorithm exists to do a task—has been solved; what must forever
be unsolvable is the task itself.
Examples of Decision Problems
We will look at some decision problems that have been answered.
example 44
Does an algorithm exist to decide, given integers a, b, and c, whether a
2
= b
2
+ c
2
?
Clearly, this question is a solvable decision problem. The algorithm consists of
multiplying b by itself, multiplying c by itself, adding the two results, and comparing
the sum with the result of multiplying a by itself.
Obviously, Example 44 is a rather trivial decision problem. Historically, much
of mathematics has concerned itself at least indirectly with finding positive solutions to decision problems, that is, producing algorithms. Negative solutions to
decision problems arose only in the twentieth century.
example 45
One of the earliest decision problems to be formulated was Hilbert’s tenth problem, tenth in a list of problems David Hilbert posed to the International Congress
of Mathematicians in 1900. The problem is: Does an algorithm exist to decide for
any polynomial equation P(x 1 , x 2 , … , x n ) = 0 with integral coefficients whether
it has integral solutions? For polynomial equations of the form ax + by + c = 0,
where a, b, and c are integers, it is known that integer solutions exist if and only
if the greatest common divisor of a and b also divides c. Thus, for particular subclasses of polynomial equations, there might be algorithms to decide whether integer solutions exist, but the decision problem as stated applies to the whole class
of polynomial equations with integer coefficients. When this problem was posed
and for some time after, the general belief was that surely an algorithm existed and
the fact that no one had found such an algorithm merely implied that it must be
difficult. In the mid-1930s, a startling result by Kurt Gödel, described in the next
example, began to cast doubt on this view. It was not until 1970, however, that this
problem was finally shown to be unsolvable.
Modeling Arithmetic, Computation, and Languages
Definition DECision ProBLEM
A decision problem asks if an algorithm exists to decide whether individual
statements from some large class of statements are true.
The solution to a decision problem answers the question of whether an
algorithm exists. A positive solution consists of proving that an algorithm exists, and it is generally given by actually producing an algorithm that works. A
negative solution consists of proving that no algorithm exists. Note that this
statement is much stronger than simply saying that a lot of people have tried
but no one has come up with an algorithm—this might simply mean that the
algorithm is hard. It must be shown that it is impossible for anyone ever to come
up with an algorithm. When a negative solution to a decision problem is found,
the problem is said to be unsolvable, uncomputable, or undecidable. This terminology can be confusing because the decision problem itself—the question
of whether an algorithm exists to do a task—has been solved; what must forever
be unsolvable is the task itself.
Examples of Decision Problems
We will look at some decision problems that have been answered.
example 44
Does an algorithm exist to decide, given integers a, b, and c, whether a
2
= b
2
+ c
2
?
Clearly, this question is a solvable decision problem. The algorithm consists of
multiplying b by itself, multiplying c by itself, adding the two results, and comparing
the sum with the result of multiplying a by itself.
Obviously, Example 44 is a rather trivial decision problem. Historically, much
of mathematics has concerned itself at least indirectly with finding positive solutions to decision problems, that is, producing algorithms. Negative solutions to
decision problems arose only in the twentieth century.
example 45
One of the earliest decision problems to be formulated was Hilbert’s tenth problem, tenth in a list of problems David Hilbert posed to the International Congress
of Mathematicians in 1900. The problem is: Does an algorithm exist to decide for
any polynomial equation P(x 1 , x 2 , … , x n ) = 0 with integral coefficients whether
it has integral solutions? For polynomial equations of the form ax + by + c = 0,
where a, b, and c are integers, it is known that integer solutions exist if and only
if the greatest common divisor of a and b also divides c. Thus, for particular subclasses of polynomial equations, there might be algorithms to decide whether integer solutions exist, but the decision problem as stated applies to the whole class
of polynomial equations with integer coefficients. When this problem was posed
and for some time after, the general belief was that surely an algorithm existed and
the fact that no one had found such an algorithm merely implied that it must be
difficult. In the mid-1930s, a startling result by Kurt Gödel, described in the next
example, began to cast doubt on this view. It was not until 1970, however, that this
problem was finally shown to be unsolvable.