However unapproachable these problems may seem to us and however helpless we stand before them, we have, nevertheless, the firm conviction that their solution must follow by a finite number of purely logical processes$\ldots$This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason; for in mathematics there is no ignorabimus.
In this chapter we consider the question of what problems can and cannot be solved by mechanical computation. This is the question of computability: a problem is computable if it can be solved by some algorithm; a problem that is noncomputable cannot be solved by any algorithm.
Section 12.1 considers first the analogous question for declarative knowledge: are there true statements that cannot be proven by any proof? Section 12.2 introduces the Halting Problem, a problem that cannot be solved by any algorithm. Section 12.3 sketches Alan Turing's proof that the Halting Problem is noncomputable. Section 12.4 discusses how to show other problems are noncomputable.