Computability: several notions#
We now turn to some of the main issues that drive our subject. First of all, there is the matter of giving a mathematical definition to the intuitive concept of computability. To see one of the issues, consider the diagram below.
The inside region represents what could be “computed” at the time of this writing. It is marked by a jagged boundary, since this border depends on the sofware and hardware, and on top of that it is time-dependent. It is very hard to have a detailed and useful scientific study of such a concept. Of more interest is the red boundary, the division between mathematical matters which are “in principle” computable, and those which are out of this boundary. What we mean by “in principle” here is that we want to set aside all considerations of time and space limitations, except that everything must take only finitely many steps, and use only finitely much space.
Models of computation#
Even with the distinction between “in practice” and “in principle” computability, and even with our decsion to focus on “in principle” computability, there still is the question of how to pin down this notion. How should it be defined in order to get a mathematical theory off the ground? Our answer in this text is a variation on a standard practice. We will do two things:
First, we will provide a very concrete definition of computability based on a machine model. We have already begun this with our introduction of 1# and its associated notion of functions computed by programs. There are other ways to do just this, and the machine models involved have names like Turing machine or register machine. (Our text register machine is of course very close to an ordinary register machine; the main difference is that we have an alphabet with two symbols instead of just one, and our language of instructions and programs is identical to the language of words stored in the registers. We will see later what differences come to.)
Second, we argue that in a very real sense, it doesn’t matter which concrete model of computation one works with, “it comes to the same thing”. This is the second part of the Church-Turing Thesis. One way to make this concrete is to take computability on the natural numbers as a sort of reference point, and then check that all of the concrete models give the same notion of computable partial functions. It would take quite some work to provide the evidence that all of the models of computation lead to the same class of computable partial functions of numbers, and so we are not going to do much of it. The first part of this same Church-Turing Thesis is that this class of computable partial functions of numbers is the correct formalization of the intuitive notion of a computable function.
Finite vs. infinite#
As is clear from our picture at the top of this page, much of the action in the subject is ultimately do to the tension between the finite and the infinite. Indeed, at some level the distinction between the “in principle computable” and “not-even-in-principle computable” corresponds to the difference between (a) problems with a search space that at first looks infinite but which can be reduced to a finite space, and (b) problems with an unavoidably infinite search space.
In more detail: suppose that we are looking for a cycle in a given finite graph \(G\). At first glance, the length of the smallest cycle could look to be arbitrarily large. But upon further reflection, if \(G\) has \(n\) points, then every cycle of length larger than \(n\) must have a repeated element and thus a sub-cycle of length at most \(n\). So the search space in this problem is finite. On the other hand, in the example problems which turn out to be undecidable, the space is unavoidably infinite.
There is one important principle related to finiteness which is worth mentioning and understanding.
Proposition 1
Every finite set is decidable.
The proof basically comes down to a table look-up.
For many, this result is uninspiring, even wrong somehow. So it is worthwhile to understand both the result itself and the objections.