Theory of Computation

2.7 DIAGONALIZATION REVISITED; UNSOLVABILITY VIA REDUCTIONS

This section further develops the theory of computability and uncomputability by developing tools—in particular, reducibility—that are more sophisticated than the ones we encountered so far in this volume, toward discovering undecidable and non c.e. problems. We also demonstrate explicitly that diagonalization is at play in a number of interesting examples.

As we mentioned in the Preface and elsewhere already, the aim of computability is to “formalize” the concept of “algorithm” and then proceed to classify problems as decidable vs. undecidable and verifiable vs. unverifiable.

We continue taking—by definition—the term “algorithm” to mean URM program, and computable (partial) function to mean a URM-computable function, or equivalently, one that has a -derivation (cf. 2.3.0.11). Thus proving that such and such a problem x A does not have an “algorithmic solution”, or is not even verifiable, becomes mathematically precise: We need to show that A _* or A _*, respectively.

Church has gone a step further, and observing that all known ...