$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

5.4: Representable Functions and Computer Programs

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

In this section we shall investigate the relationship between representable functions and computer programs. Our discussion will be rather informal and will rely on your intuition about computers and calculations.

One of the reasons that we must be rather informal when discussing computation is that the idea of a calculation is rather vague. In the mid-1930s many mathematicians developed theoretical constructs that tried to capture the idea of a calculable function. Kurt Gödel's recursive functions (now often called computable functions), the Turing Machines of Alan Turing, and Alonzo Church's $$\lambda$$-calculus are three of the best-known models of computability.

One of the reasons that mathematicians accept these formal constructs as accurately modeling the intuitive notion of calculability is that all of the formal analogs of computation that have been proposed have been proved to be equivalent, and each of them is also equivalent to the notion of representability that we defined in the last section. Thus it is known that a function is Turing computable if and only if it is general recursive if and only if it is $$\lambda$$-computable. It is also known that these formal notions are equivalent to the idea of a function being computable on a computer, where we will say that a function $$f$$ is computable on an idealized computer if there is a computer program $$P$$ such that if the program $$P$$ is run with input $$n$$, the program will cause the computer to output $$f \left( n \right)$$ and halt.

Thus the situation is like this: On one hand, we have an intuitive idea of what it means for a function to be effectively calculable. On the other hand, we have a slew of formal models of computation, each of which is known to be equivalent to all of the others:

$\begin{array}{c||c} \text{Intuitive Notion} & \text{Formal Models} \\ \hline \hline & \text{Representable function} \\ & \text{Computable function} \\ \text{Calculable function} & \lambda-\text{Computable function} \\ & \text{Turing-computable function} \\ & \text{Computer-computable function} \\ & \vdots \end{array}$

So why do we say that the idea of a calculation is vague? Although all of the current definitions are equivalent, for all we know there might be a new definition of calculation that you will come up with tonight over a beer. That new definition will be intuitively correct, in the sense that people who hear your definition agree that it is the "right" definition of what it means for a person to compute something, but your definition may well not be equivalent to the current definitions. This will be an earthshaking development and will given logicians and computer scientists plenty to think about for years to come.

You will go down in history as a brilliant person with great insight into the workings of the human mind!

You will win lots of awards and be rich and famous!

All right, we admit it. Not rich. Just famous.

OK. Maybe not famous. But at least well known in logic and computer science circles.

But until you have that beer we will have to go with the current situation, where we have several equivalent definitions that seem to fit our current understanding of the word computation. So our idea of what constitutes a computation is imprecise, even though there is precision in the sense that lots of people have thought about what the definition ought to be, and every definition that has been proposed so far has been proved (precisely) to be equivalent to every other definition that has been proposed.

Church's Thesis is simply an expression of the belief that the formal models of computation accurately represent the intuitive idea of a calculable function. We will state the thesis in terms of representability, as we have been working with representable functions and representable sets.

Church's thesis

A total function $$f$$ is calculable if and only if $$f$$ is representable.

Now it is important to understand that Church's Thesis is a "thesis" as opposed to a "theorem" and that it will never be a theorem. As an attempt to link an intuitive notion (calculability) and a formal notion (representability) it is not the sort of thing that could ever be proved. Proofs require formal definitions, and if we write down a formal definition of calculable function, we will have subverted the meaning of the thesis.

To add another layer to this discussion, consider the function $$f$$ that assigns to each natural number its natural number square root, if it has one. We will say that $$f \left( n \right)$$ is not defined if $$n$$ is not a square. So $$f \left( 9 \right) = 3$$ and $$f \left( 10 \right)$$ is not defined. This partial function seems to be calculable, and in fact here is some pseudo-code that would compute the output values for $$f$$: To be a little more precise, we will say that a partial function $$f : A \subseteq \mathbb{N} \rightarrow \mathbb{N}$$ is calculable if there is an algorithm or computation that, given input $$n \in \mathbb{N}$$, does exactly one of the following:

• If $$f \left( n \right)$$ is defined, the algorithm computes the correct value of $$f \left( n \right)$$, outputs $$f \left( n \right)$$ and then halts;
• If $$f \left( n \right)$$ is not defined, the algorithm runs forever without halting.

So if the function $$f$$ is total and calculable, there is an algorithm which will compute $$f \left( n \right)$$ for any input $$n$$, but if $$g$$ is partial and calculable, then $$g$$'s algorithm will halt when $$g \left( n \right)$$ is defined, but will run forever if $$g \left( n \right)$$ is not defined.

We will say that a set $$S \subseteq \mathbb{N}$$ is calculable if its characteristic function, $$\chi_S$$, is calculable. (See Exercise 5 in Section 5.3 for the definition of $$\chi_S$$.)

Since the study of computation leads rather naturally to the investigation of partial functions, Church's Thesis is often stated in terms of partial functions:

church's thesis

A partial function $$f$$ is calculable if and only if $$f$$ is weakly representable.

The tie between the two versions of Church's Thesis lies in Proposition 5.3.6. Using that proposition, it is easy to see that the total function version of Church's Thesis follows immediately from the partial function version.

For an example of the sort of question that can be addressed by thinking about calculable sets and functions, consider the following:

The class of calculable sets of $$\mathbb{N}$$ can be extended by looking at the collection of sets such that there is a computer program which will tell you if a number is an element of the set, but does not have to do anything at all if the number is not an element of the set. Informally, a set $$A \subseteq \mathbb{N}$$ is said to be semi-calculable if there is a computer program $$P$$ such that if $$a \in A$$, program $$P$$ returns 0 on input $$a$$, and if $$a \notin A$$, program $$P$$ does not halt when given input $$a$$. You can check that this is equivalent to saying that the partial function $$\overset{\smallsmile}{\chi}_A : A \rightarrow \mathbb{N}$$ that takes on the value 0 for every element of its domain is calculable.

If we accept Church's Thesis, it is easy to argue that set $$A$$ is representable if and only if both $$A$$ and $$\mathbb{N} - A$$ are semi-calculable, as you are asked to do in Exercise 6. Other exercises provide a little more practice in working with semi-calculable sets.

The study of computable functions is an important area of mathematical logic, and emphasizes the tie between logic and computer science. Chapter 7 is devoted to presenting an introduction to computable functions that leads to a proof of Gödel's Incompleteness Theorem. In this setting, the statement of the Incompleteness Theorem amounts to the statement that the collection of sentences that are provable-from-$$\Sigma$$, where $$\Sigma$$ is an extension of $$N$$ that is decidable and true-in-$$\mathfrak{N}$$, is a semi-computable set that is not computable. Thus there is a significant difference between the collection of computable sets and the collection of semi-computable sets. Another text that emphasizes computability in its treatment of Gödel's Theorem is [Keisler and Robbin 96].

So is Church's Thesis true? We can say that all of the evidence to date seems to suggest that Church's Thesis is true, but we are afraid that is all the certainty that we can have on that point. We have over 70 years' experience since the statement of the thesis, and over 3000 years since we started computing functions, but that only counts as anecdotal evidence. Even so, most, if not all, of the mathematical community accepts the identification of "computable" with "representable" and thus the community accepts Church's Thesis as an article of faith.

Exercises

1. We defined calculable functions and semi-calculable sets in this section, but the definitions are not set off in their own block and given fancy numbers, like "Definition 5.4.2." Why didn't we make the definitions official-looking like that?
2. Using Church's Thesis, show that $$A \subseteq \mathbb{N}$$ is calculable if and only if $$A$$ is representable. Then show that $$A$$ is semi-calculable if and only if $$A$$ is weakly representable.
3. (a) Show that $$A \subseteq \mathbb{N}$$ is semi-calculable if and only if $$A$$ is listable, where a set is listable if there is a computer program $$L$$ such that $$L$$ prints out, in some order or another, the elements of $$A$$.
(b) Show $$A \subseteq \mathbb{N}$$ is calculable if and only if $$A$$ is listable in increasing order.
4. Suppose that $$A \subseteq \mathbb{N}$$ is infinite and semi-calculable and show that there is an infinite set $$B \subseteq A$$ such that $$B$$ is calculable.
5. Show that $$A \subseteq \mathbb{N}$$ is semi-calculable if and only if there is a $$\Sigma$$-formula $$\phi \left( x \right)$$ such that $$\phi$$ defines $$A$$.
6. Use Church's Thesis to show that a set $$A$$ is representable if and only if both $$A$$ and $$\mathbb{N} - A$$ are semi-calculable. [Suggestion: First assume that $$A$$ is representable. This direction is easy. For the other direction, the assumption guarantees the existence of two programs. Think about writing a new program that runs these two programs in tandem - first you run one program for a minute, then you run the second program for a minute....]