Computability: initial remarks

Attention

Note for instructors

The sections of this chapter are general background and motivation. They could be read at the beginning of a course, but more likely they will be used on an “as needed” basis. I say this because not every course will need all of the background sections that are here. For example, if a course will not contain the concrete undecidability results that near the end of the book, there is no real reason to motivate them in the beginning. In other words, the course could begin with the work on 1# in the next chapter.

We begin with 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

1. 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.

2. Let \(2 = \{ \mbox{True}, \mbox{False}\}\) be the set of truth values, and let \(g: N \to 2\) be given by

\[ g(n) = \mbox{True} \quad \mbox{if and only if} \quad \mbox{Harriet Tubman liked $n$}. \]

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.

3. Let \(h: N \to N\) be given by

\[ h(n) = \mbox{the least $m > n$ such that $m$ and $m+2$ are both prime numbers} \]

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

\[ \{(0,1), (1,2), (2,3), \ldots, (n,n+1), \ldots\}. \]

Here are two functions from positive numbers to positive numbers:

\[ f(m,n) = \mbox{the greatest common divisor of $m$ and $n$} \]

\[ g(m,n) = \mbox{the product $m n$ divided by the least common multiple of $m$ and $n$} \]

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

Total vs. partial functions

Let \(A\) and \(B\) be sets. A function from \(A\) to \(B\) is a way to take each element of \(A\) to some element of \(B\). It must be defined for all \(a\in A\), and we emphasize this point by saying that it is total. A partial function from \(A\) to \(B\) is a total function from a subset of \(A\) to \(B\). Another way to say this: \(f\) is a partial function if some (but perhaps not all) of the elements of \(A\) are taken to elements of \(B\). We say that \(f(a)\) is defined in this case, and we write \(f(a)\!\!\downarrow\). Finally, the domain of \(f\) is \(\{ a\in A \colon f(a)\!\!\downarrow\}\).

Please note that every total \(f\colon A\to B\) is automatically partial.

Another choice point is whether to stick to total functions or to allow partial functions in our study. We opt to include partial functions in a big way. That is, we are foregrounding the partial functions. When a function is total, we make a special mention of this. (To contrast, with \(A = B = \) the real numbers, the function \(f(x)= \frac{1}{x}\) is not defined at \(x = 0\). But usually one pretends that it is total and then makes a special note afterwards about \(0\). Here, every function is presumed to be merely partial, and the total functions are the ones that get a special notice.)

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.

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,

\[ [\![c(n)]\!](m) = n \mbox{ for all $m$} \]

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.