RecursiveFunctions.pdf are notes (some parts sketchy) on recursive functions, aiming to demonstrate that the formalism of recursive functions can be used as a programming language. First, some basic utilities are defined as recursive functions. Then it is explained how recursion corresponds to (for) loops.

MoreGödelNotes.pdf addresses in particular the point of what it means for a predicate logic formula to represent a function, and how that combines with Gödel's diagonalisation function to provide self-reference. (The proofs as written during the lecture were probably a bit easier to read, however.)

Not covered in either is the trick (Gödel's $β$ -function) that allows recursion to be represented in Peano arithmetic: if

${\begin{aligned} f (x_{1}, \dots, x_{n}, 0) = & g (x_{1}, \dots, x_{n}) \\ f (x_{1}, \dots, x_{n}, y + 1) = & h (x_{1}, \dots, x_{n}, y, f (x_{1}, \dots, x_{n}, y)) \end{aligned}$

then we need to represent using only some constant number of $N$ -valued variables an arbitrarily long sequence $z_{0}, \dots, z_{k}$ of natural numbers, namely those numbers satisfying

${\begin{aligned} z_{0} = & g (x_{1}, \dots, x_{n}) \\ z_{y + 1} = & h (x_{1}, \dots, x_{n}, y, z_{y}) for y = 0, \dots, k - 1 \end{aligned}$

Gödel's trick at this step relies on the fact that we don't have to use the same encoding for all sequences—it's fine to introduce parameters into the encoding, and sufficient that there for every finite sequence exists some combination of parameters that manage to encode it. Thus he uses the Chinese Remainder Theorem to encode each $z_{y}$ as the remainder modulo $a + b y$ of some huge number $c$ , where $(a, b, c)$ becomes the trio of variables encoding the sequence $z_{0}, \dots, z_{k}$ . Lengthening the sequence or increasing some number in the sequence may require switching $a$ and $b$ , and there is no obvious algorithm for updating $a$ and $b$ to accomodate such changes, but in order to formally make a claim it is sufficient that such numbers can be found for any given sequence $z_{0}, \dots, z_{k}$ .