Book Reviews

The theory of recursively solvable decision problems, the theory of recursively unsolvable decision problems, the theory of decidable theories, and the theory of undecidable theories are basic to modern logic. The theories of unsolvable problems and undecidable theories establish formal frameworks for questions that cannot, in principle, be resolved by computational means as we understand them. They are analogous to the simpler. impossibility problems involving more restricted means of construction, which the ancients bequeathed to us: the so-called duplication of the cube, the squaring of the circle, or the trisecting of an arbitrary angle by Euclidean ruler and compasses alone, for example. Indeed, recursively unsolvable problems–products of a dogged determination to understand the nature of computation–are analogous to the simpler problem of the impossibility of solving arbitrary polynomial equations by rational operations and radicals, that is, by allowing expanded computational means.