Computability Theory

Recursive Enumerability 81

Proof. We have x ∈ K ⇐⇒ hx, xi ∈ H. a

Thus the halting problem, despite being a precisely formulated problem, is unsolv-

able. We will see other such problems (i.e., other noncomputable relations). Moreover,

there are unsolvable problems in other parts of mathematics. In Chapter 5, we will see

that the problem of deciding, given a sentence in arithmetic, whether it is true or false,

is unsolvable.

Digression: “Hilbert’s tenth problem” is the problem of deciding, given a polynomial

equation in many variables with integer coefficients, whether or not it has a solution

in the integers. (For example, the equation x

2

= 9y

2

+ 18y