O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 images-derivation (cf. 2.3.0.11). Thus proving that such and such a problem x images A does not have an “algorithmic solution”, or is not even verifiable, becomes mathematically precise: We need to show that A images images* or A *, respectively.

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required