**Maintainer:**admin

**Any errors in the final exam due to the use of these notes will not be given any special consideration. Prakash has not endorsed these notes and is not responsible for any mistakes in them.** You can find Prakash's own notes on this topic here.

*1*Introduction¶

The foundation of modern programming languages was pioneered both by Alan Turing, with his idea of an universal Turing machine that can take an algorithm as input and execute it, and by Alonzo Church, with his $\lambda$-calculus. These days, algorithms have become such a natural concept that it seems strange to think that when we devise an algorithm, we are creating the most complex thing envisioned by the human mind. And indeed, the typical algorithm is so complex that we can only understand it via compositionality — by understanding the individual elements, and composing them together accordingly.

To that end, we will now study Gödel universal functions. We'll see that we can take programs and combine them to create more programs in a computable way.

*2*Universal functions¶

Consider a binary function $U: \mathbb{N}^2 \to \mathbb{N}$. $U$ is **universal** for unary computable functions if:

- For all computable functions $f: \mathbb N \to \mathbb N$, there exists an $n$ such that $U_n = f$, i.e., $\forall xU_n(x) = U(n,x)=f(x)$ (so every function is encoded within $U$).
- $U$ is itself computable.

Of course, simply defining a term does not guarantee that such a thing exists! It so happens that universal functions do, in fact, exist. However, we will not be proving that in this lecture. (To convince yourself, think about the fact that interpreters exist.)

*2.1*Implications for non-terminating programs¶

What if we could write a programming language that prevents you from writing programs that never terminate? In fact, we *can* write such a language, simply by incorporating strict typing in a particular way (e.g., strictly-typed lambda calculus). But there aren't any programming languages like this in use. Why not? Well, if we eliminated the possibility of being able to write programs that never terminate, we would necessarily eliminate the possibility of writing certain programs that *do* terminate.

This arises as a result of the fact that any total computable function of 2 arguments cannot be universal for all total unary computable functions, which we can prove by contradiction: Suppose there is a $U$ that is universal for all total unary computable functions. We define a total computable function $d: \mathbb N \to \mathbb N$ by $d(n) = U(n, n) + 1$. Because $U$ is total, $d$ will terminate. But $d$ is not reproduced within $U$, via this simple diagonal argument. Thus $d(n)$ cannot be realised by $U$!

*TODO: Clarify the link between the first and second paragraphs.*

*2.2*Gödel numbering¶

If $S$ is any set, then a map $V$ of the form $V:\mathbb N \to S$ is called a **numbering**. We define $V$ to be a function, so that each $n \in \mathbb N$ is associated with exactly one element in $S$; however, it is not necessarily injective, so there can be multiple numbers associated with each element in $S$^{needs confirmation}.

Any universal function defines a numbering of unary computable functions.

*2.3*Composing functions¶

We now turn our attention to the problem of **composing** functions. That is, we want to create a total computable function $C$ which takes two functions as input and returns one function which is equivalent to running both input functions. In mathematical notation:

$$\forall p, q, x \; (U_P\circ U_q)(x) = U(p, U(q, x)) = U_{C(p, q)}(x) = U(C(p, q), x) \tag{is this correct?}$$

*2.4*Gödel universal functions¶

A **Gödel universal function** (GUF) is a binary universal function for the class of unary computable functions such that for any binary computable function $V$, there exists a total computable function $\sigma$ such that $\forall x, m, V(m, x) = G(\sigma(m), x)$. So it must be universal in the usual sense, but it must also be able to simulate all binary functions in conjunction with some unary function.

*2.4.1*Proof of existence¶

As with universal functions, we need to prove that such a thing exists. To do so, consider the fact that we can easily create an injective, surjective and computable function, which we'll call $\tau$, from $\mathbb N^2$ to $\mathbb N$ and vice versa. (The construction of $\tau$ is omitted in these notes because the one given in class doesn't quite work. Left as an exercise for the reader.) Suppose $\tau(i, j) = $ some function involving $i$ and $j$. Then, to invert this, we define the functions $\text{fst}:\mathbb N \to \mathbb N$ and $\text{snd}: \mathbb N \to \mathbb N$ such that $\tau(\text{fst}(n), \text{snd}(n)) = n$, $\text{fst}(\tau(i, j)) = i$ and $\text{snd}(\tau(i, j)) = j$.

Next, given any universal computable function $U$, we define some function $G: \mathbb N^2 \to \mathbb N$ by

$$G(n, x) = U(\text{fst}(n), \tau(\text{snd}(n), x))$$

We need to show that $G$ is indeed a GUF. Let $V$ be a binary computable function. We define $f: \mathbb N \to \mathbb N$ by

$$f(k) = V(\text{fst}(k), \text{snd}(k))$$

Now, we need to find a total computable function $\sigma: \mathbb N \to \mathbb N$ such that $V(m, x) = G(\sigma(m), x)$. $U$ is universal, so there exists some $i$ such that $f(k) = U(i, k)$. We define $\sigma$ by $\sigma(m) = \tau(i, m)$. Then: $G(\sigma(m), x) = G(\tau(i, m), x) = U(i, \tau(m, x) = f(\tau(m, x)) = V(m, x)$. $\blacksquare$

*2.4.2*Relation to function composition¶

Let $G$ be a GUF. Then there exists a $C: \mathbb N^2 \to \mathbb N$ such that $C$ is a total computable function and $\forall p, q, x$, $(G_p\circ G_q)(x) = G(p, G(q, x)) = G(C(p, q), x)$. Define $V(m, x) = G(\text{fst}(m), G(\text{snd}(m), x))$. (Alternatively, and equivalently, we could define $V$ by $V(\tau(m, n), x) = G(m, G(n, x))$). Then there exists $\sigma$ such that $V(m, x) = G(\sigma(m), x))$ by the definition of a GUF. Thus GUFs immediately give computable compositions of codes, allowing us to abstract complicated algorithms into their functional specs. This in turn allows us to think of functions as black boxes, whereby we only need to know their inputs and expected outputs and don't have to know their implementations at all.

Of course, not all functions can be thought of this way. Particularly, once you introduce non-determinism into the mix, it becomes clear that a program's functional spec is nowhere near sufficient to accurately represent the program.