Algorithms and partial functions

1.1 The Entscheidungsproblem

Algorithms have been used since antiquity — Euclid’s algorithm for the greatest common divisor, the sieve of Eratosthenes, Gaussian elimination — without any need for a definition of the word. As long as one only wishes to show that a problem can be solved mechanically, it suffices to exhibit a procedure that everybody accepts as mechanical.

The situation changed with the foundational program of Hilbert. In 1928, Hilbert and Ackermann formulated the Entscheidungsproblem: find a procedure which, given a formula of first-order logic, decides in finitely many steps whether this formula is universally valid. Gödel’s incompleteness theorems (1931) made a positive answer increasingly implausible. But a negative answer requires proving that no algorithm solves the problem, and a statement about all algorithms can only be proved once the class of algorithms has been defined mathematically.

Several definitions were proposed between 1931 and 1936:

• the general recursive functions of Herbrand and Gödel (1934), studied systematically by Kleene;
• the λ-definable functions of Church and Kleene (1933–1936);
• the Turing machines (1936), together with the closely related machines of Post (1936).

Church (1936) and Turing (1936) independently gave a negative solution to the Entscheidungsproblem. The three classes of functions were quickly proved to coincide. Turing’s analysis of what a human computer can do was decisive in convincing the community — including Gödel — that the definition was the right one.

Note that the first electronic computers were built a decade later. The notion being formalized is that of a function computable by a human following a finite set of instructions mechanically, with unlimited paper and time.

1.2 Features of an algorithm

Any proposed definition should respect the following features of the informal notion.

1. Finite description. An algorithm is described by a finite text, fixed in advance, independent of the input.
2. Discrete and deterministic steps. The computation proceeds in steps. At each step, the next action is completely determined by the current situation, and each action is elementary — it requires no insight.
3. Unbounded resources. No bound is fixed in advance on the number of steps or on the amount of memory. A computation which terminates has however only performed finitely many steps, and therefore used only finitely much memory.
4. Possible non-termination. Nothing guarantees that a computation terminates. An algorithm therefore defines a partial function, undefined on the inputs on which the computation does not terminate.

Points 3 and 4 distinguish computability theory from complexity theory: we study what can be computed in principle, not what can be computed within given resources. Point 4 is not a defect of the definitions. We will see in the course on fundamentals that it cannot be avoided: there is no programming language with a computable interpreter whose programs compute exactly the total computable functions.

1.3 Partial functions

Throughout the course, $\nat = \{0, 1, 2, \dots\}$, and $\vec x$ abbreviates a tuple $(x_1, \dots, x_k)$ whose length is clear from the context.

Definition 1.1.#

A partial function $f : \nat^k \rightharpoonup \nat$ is a function from a subset $\dom f \subseteq \nat^k$, its domain, to $\nat$. We write $f(\vec x)\converge$ (”$f$ converges on $\vec x$”) if $\vec x \in \dom f$, and $f(\vec x)\diverge$ (”$f$ diverges on $\vec x$”) otherwise. We write $f(\vec x)\converge = y$ when $\vec x \in \dom f$ and $f(\vec x) = y$. A partial function is total if $\dom f = \nat^k$.

Total functions are particular partial functions. The image of $f$ is $\operatorname{im} f = \{ f(\vec x) : \vec x \in \dom f \}$. The empty function, with empty domain, is denoted $\emptyset$ when no confusion is possible.

When partial functions are composed, an expression may be undefined. We adopt the following convention: an expression built from partial functions is defined only if all its subexpressions are defined. For instance, $g(f(x))\converge$ requires $f(x)\converge$ and $g$ to converge on the value $f(x)$. In particular, $0 \cdot f(x)$ is undefined when $f(x)\diverge$: we never evaluate an expression “lazily”.

Notation 1.2.#

For two expressions $e_1, e_2$ built from partial functions, we write $e_1 \simeq e_2$ (Kleene equality) to mean that either both are undefined, or both are defined and have the same value.

For instance, two partial functions $f, g$ are equal if and only if $f(\vec x) \simeq g(\vec x)$ for all $\vec x$. Some authors simply write $=$ for $\simeq$; we will do so in later courses, when no ambiguity can arise.

1.4 Coding finite objects by integers

Algorithms manipulate finite objects: integers, but also tuples, finite sequences, strings, formulas, graphs, and programs. We will mostly study functions on $\nat$. This is no restriction, because all these objects can be coded by integers in such a way that the usual operations on them become computable operations on the codes. The basic tool is a bijection between $\nat^2$ and $\nat$.

Definition 1.3.#

Cantor’s pairing function is the function $\langle \cdot, \cdot \rangle : \nat^2 \to \nat$ defined by

$$\langle x, y \rangle = \frac{(x+y)(x+y+1)}{2} + y.$$

The pairs are enumerated diagonal by diagonal: $\langle 0,0 \rangle = 0$, $\langle 1,0 \rangle = 1$, $\langle 0,1 \rangle = 2$, $\langle 2,0 \rangle = 3$, $\langle 1,1 \rangle = 4$, $\langle 0,2 \rangle = 5$, and so on. Write $T(n) = n(n+1)/2$ for the $n$-th triangular number.

Proposition 1.4.#

The function $\langle \cdot, \cdot \rangle$ is a bijection from $\nat^2$ to $\nat$.

Proof of Proposition 1.4.

Fix $z \in \nat$. Since $T$ is strictly increasing with $T(0) = 0$, there is a unique $n$ such that $T(n) \leq z < T(n+1) = T(n) + n + 1$. Let $y = z - T(n)$, so that $0 \leq y \leq n$, and let $x = n - y$. Then $x + y = n$ and $\langle x, y \rangle = T(n) + y = z$, so the function is surjective.

For injectivity, suppose $\langle x, y \rangle = \langle x', y' \rangle = z$, and let $n = x + y$, $n' = x' + y'$. Since $0 \leq y \leq n$, we have $T(n) \leq z \leq T(n) + n < T(n+1)$, and similarly for $n'$. By uniqueness of $n$ above, $n = n'$; then $y = z - T(n) = y'$ and $x = n - y = x'$.

The inverse functions $\pi_0, \pi_1 : \nat \to \nat$ with $\pi_0(\langle x, y \rangle) = x$ and $\pi_1(\langle x, y \rangle) = y$ are computed by the procedure of the proof: find $n$ with $T(n) \leq z < T(n+1)$ by trying $n = 0, 1, \dots, z$, then set $y = z - T(n)$ and $x = n - y$. Only a bounded search is needed, since $n \leq z$. This remark will become important when we study primitive recursive functions.

Iterating the pairing function codes tuples of any fixed length: $\langle x_1, x_2, x_3 \rangle = \langle x_1, \langle x_2, x_3 \rangle \rangle$, and in general $\langle x_1, \dots, x_{k+1} \rangle = \langle x_1, \langle x_2, \dots, x_{k+1} \rangle \rangle$. For each $k \geq 1$ this gives a bijection $\nat^k \to \nat$. Finite sequences of arbitrary length require a little more care, since the length must be recoverable from the code; this is done in the lesson Coding finite sequences.

Strings over a finite alphabet $\{a_1, \dots, a_m\}$ are coded by reading them as numerals in base $m$ with digits $1, \dots, m$ (bijective numeration): the string $a_{i_1} \cdots a_{i_\ell}$ is coded by $\sum_{j=1}^{\ell} i_j\, m^{\ell - j}$, which defines a bijection between strings and $\nat$, the empty string being coded by $0$. Programs, being strings, are coded the same way. With these codings, a function on finite objects is called computable if the corresponding function on codes is.

1.5 Exercises

Exercise 1.5 ★.

Show that the function $\nat^2 \to \nat$, $(x, y) \mapsto 2^x (2y + 1) - 1$ is a bijection. Compare it with Cantor’s pairing function: which one is more economical, in the sense of the size of $\langle x, x \rangle$ as a function of $x$?

Solution

Every integer $z \geq 1$ is uniquely of the form $2^x \cdot m$ with $m$ odd, that is $m = 2y + 1$. So $(x, y) \mapsto 2^x(2y+1)$ is a bijection from $\nat^2$ onto $\nat \setminus \{0\}$, and subtracting $1$ gives a bijection onto $\nat$. On the diagonal, $2^x(2x+1) - 1$ grows exponentially, whereas $\langle x, x \rangle = x(2x+1) + x$ is quadratic. Cantor’s pairing is a polynomial bijection; by a theorem of Fueter and Pólya, it is, up to exchanging the coordinates, the only quadratic polynomial bijection from $\nat^2$ to $\nat$.

Exercise 1.6 ★.

Show that $\langle x, y \rangle \geq x$ and $\langle x, y \rangle \geq y$ for all $x, y$, with equality only when $x = y = 0$, or $(x, y) = (1, 0)$ for the first inequality.

Solution

$\langle x, y \rangle = T(x+y) + y$. Since $T(n) \geq n$, we get $\langle x, y \rangle \geq x + y + y \geq y$, and $\langle x, y \rangle \geq T(x) \geq x$. Since $\langle x, y \rangle \geq x + 2y$, equality $\langle x, y\rangle = x$ forces $y = 0$, and then $T(x) = x$, i.e. $x \in \{0, 1\}$. Equality $\langle x, y \rangle = y$ forces $T(x+y) = 0$, i.e. $x = y = 0$.

1.6 Notes and references

The Entscheidungsproblem is formulated in Hilbert and Ackermann’s textbook Grundzüge der theoretischen Logik (Springer, 1928). Its negative solution was obtained independently by Church and by Turing in 1936. The quadratic polynomial bijections $\nat^2 \to \nat$ were determined by Fueter and Pólya (1923): up to the exchange of coordinates, Cantor’s pairing function is the only one.

• A. Church, An unsolvable problem of elementary number theory, American Journal of Mathematics 58 (1936), 345–363.
• A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society (2) 42 (1936), 230–265.
• R. Soare, Turing Computability: Theory and Applications, Springer, 2016, chapter 1, for a historical account.