George Tourlakis - Computability

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

This volume is mostly about the theoretical limitations of computing: On one hand, we investigate what we cannot do at all through the application of mechanical (computational) processes and why. This is the domain of computability theory. On the other hand, we study some problems that admit only extremely inefficient mechanical solutions and explore why this is so. For example, is it always the enormous size of the output that makes a solution computationally inefficient? We will see (Chap. ) that this is a deeper phenomenon and will discover that for any amount of resources that we might a priori decide to spend on any computation, we can build a computable function so that every program we might employ to compute it will require, for all but a finite number of inputs, more resources than we had originally set aside and this remains true even if we restrict the outputs of our function to be only the numbers 0 or 1. The study of this phenomenon belongs to (computational) complexity theory.

Admittedly, anyone who has programmed a computer, or studied some discrete mathematics, or has done both, will normally have no trouble recognising a mechanical (computational) process (or algorithm) when they see one. For example, they ought to readily recognise Euclids algorithm for finding the greatest common divisor,gcd(a, b), as such a process. The same is true of the binary search algorithm used to search for a given value in a sorted (ascending or descending order) finite array of values.

Most of us will define a mechanical process as any finitely described, precise, step-by-step process, usually performed in terms of a menu of permissibleinstructions, which must be carried out in a certain order. Moreover, these instructions must be extremely simple, and such that they can be mechanically carried out unambiguously, say, by pencil and paper. Here are two examples of instructions that meet our informal requirements stated in this paragraph: (1) change the i-th digit of a (natural) number written in decimal notation by adding 1 to it (where adding 19 makes it 0 but changes nothing else); another one: (2) add 1 to a natural number n.

The simpler that these mechanical instructions are the easier it is for reasonable people to agree that they can be carried out mechanically and precisely.

Hm. If all we want to achieve is to agree with reasonable people on the definition of an algorithm or mechanical process, then what do we need a theory of computation for? The difficulty with algorithms programs, as people who program computers call them is not so much in recognising that a process is an algorithm, or to be able to device an algorithm to solve a straightforward problem; programmers do this for a living.

The difficulty manifests itself as soon as we want to study the inherent mathematical limitations of computing. That is, when we want to prove that a particular problem, or a set of problems, admits no solution via mechanical processes admits no solution via a program. For example, consider the problems of the type check whether an arbitrary given program P computes the constant function that, for every natural number input, outputs always the same number, 42.

We will see in this volume that such a checker if we insist that it be implemented as a mechanical process does not exist, regardless of whether the constant output is 42 or some other number.

How does one prove such a thing?

We need a mathematical theory of computation, whose objects of study are programs (mechanical processes), and problems. Then we can hope to prove a theorem of the type there is no program that solves this problem.

Usually, we prove this non-existence by contradiction, using tools such as diagonalisation or reductions (of one problem to another).

We will perform this kind of task for many problems in this book and we will develop powerful tools such as Rices theorem, which, rather alarmingly, states: We cannot have a mechanical checker that decides whether an arbitrary program X has a given property or not, and this fact is true of all conceivable mathematical properties, except two: (1) The property that no program has, and (2) the property that all programs have.

By the way, a comment like this one, which is situated between two

-signs is to be considered worthy of attention.

The programs studied in a mathematical theory of computation cannot be technology-dependent nor can they be restricted by our physical world. In particular, the mathematisation of our mechanical processes will allow such processes to compute using arbitrary (natural) numbers, of