Computability: initial remarks#
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 computable function. What we mean here is that there is an intuitive definition: a function \(f:A\to B\) is intuitively computable if there is a finite set of precise instructions so that, given \(a\in A\) as an input and carrying out the instructions results in \(f(a)\) as an output. Executing the instructions has to finish in finite time on each input. The output \(f(a)\) has to be correct.
Examples/Non-Examples
Let \(N\) be the set of natural numbers \(N = \{0, 1,2, \ldots, \}\). Then the factorial function \(f(n) = n!\) is intuitively computable. One reason to believe this is that we have computer programs which do compute it. There is some program that computes this function. The program consists of precise instructions. Given a number, say \(213556669\), we could imagine carrying out those instructions to get \(213556669!\). This is true even though the usual decimal representation of \(213556669!\) is huge, and the computation of it also would take a long time (but not forever). So while we will see “edge cases” below, we want to study functions like the factorial function.
Let \(2 = \{ \mbox{True}, \mbox{False}\}\) be the set of truth values, and let \(g: N \to 2\) be given by
We mention this as a contrast to the factorial function. It is not clear that this is a precisely-defined function in the first place. What does it mean for a person to “like” a number? When are we talking about? And for someone like Harriet Tubman who lived in the past, how would we ever know? We are going to set aside such (descriptions of possible) functions.
Let \(h: N \to N\) be given by
In contrast to \(g\), this function is precisely defined. For example, \(h(8) = 11\). Moreover, \(h\) is intuitively computable: given \(n\), just look at the numbers \(m > n\), one by one, and see if each \(m\) and its associated number \(m+2\) are both prime. However, there is a hitch: it is not known whether \(g\) a total function. That is, it is not known now whether there are infinitely many twin primes. If there are, then \(h\) is a total computable function. If not, then \(h\) is still computable, but it is a computable partial function. (A partial function is a function which might not be defined at all points of its input set.)
There are two points coming from these examples. The first is that there is some concept of computability that people can agree on. That is, for some of the examples above, if we asked people in a position to think about those functions, they would tend to agree on the answers. On the other hand, if we were to want to prove something about computable functions, it would be better to have a precise definition in hand. This brings us to the second point of the examples: is that when we sit down to formalize the concept . This is a matter of mathematical modeling.
Problem which we will address
Propose a precise definition of computability.
In principle vs. in practice#
This section is about different issues to keep in mind regarding computability. Our next issue is about computability in principle vs. computability in practice. It is the topic of the diagram below.
What we have been discussing up to now is in principle computability. This is because we decided to ignore all matters having to do with time or space. This is not always a useful thing to do. What good would it be to know that a function is computable if whenever we tried to run it we would be sure that it took a billion years to compute anything? Would we even want to say that this function is computable?
The inner-most region above 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.
Intentional vs. Extensional#
Yet another choice point in our study is whether to take computability as an extensional or intensional notion. Here is what we mean: for any function \(f\), the graph of \(f\) is the set of input-output pairs of \(f\). For example, the graph of \(s(n) = n+1\) on the natural numbers is the set
Here are two functions from positive numbers to positive numbers:
These have the same graph relation, so they are extensionally the same. But the descriptions are different, so those descriptions are intensionally different.
Now the standard practice in mathematics is to regard function equality as extensional. Thus, \(f\) and \(g\) are regarded as identical. One takes function identity in the extensional sense in mathematics partly because it is clear and unproblematic, and because the alternative is very difficult to pin down.
For computability, we naturally want to do the same thing, and generally we will. But there are situations where it would be more naturally to be intensional, and we want to flag those.
does the question of whether a function is computable or not depend on how the function is presented, or is it a property of the
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.
Total vs. partial functions#
Another choice point is whether to stick to total functions or to allow partial functions in our study. We opt to include partial functions.
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.
Definition
\(Inst\) is the set of instructions (i.e., programs) of functions on algorithmically suited sets.
Exercise 1
Find a computable function \(c: Inst \times Inst \to Inst\) such that \([\![c(p,q)]\!] = [\![q]\!] \o [\![q]\!]\).
Exercise 2
Find a computable function \(con: N \to Inst\) such that \([\![c(n)]\!]\) is the constant function with value \(n\). That is,
Exercise 3
Let \(f: N \to N\) be any function with the property that if \(n \leq m\), then \(f(n) \geq f(m)\). Show that \(f\) is intuitively computable.
Summary#
Going forward
We will propose and study a precise definition of computability, starting here.
Nevertheless, there are still interesting things that one can do in computability theory with purely intuitive notions.
We will allow partial functions.
We will concentrate on in principle computability, and we will be thinking of equality extensionally.