Thursday, November 21, 2013
Universal computable functions
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.
1Introduction¶
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.
2Universal 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.1Implications 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.2Gö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.3Composing 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.4Gö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.1Proof 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.2Relation 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.