Teaching suggestions for Kleene fixed point theorem

Question

I will take over two lectures from a colleague in which we discuss fixed point theory in the context of complete partial orders, and culminates in showing the Kleene fixed point theorem (see f.e. https://en.wikipedia.org/wiki/Kleene_fixed-point_theorem).

In my opinion the course notes are not very nice: while everything is technically correct, there is no real application of the theory. They give the impression we develop an abstract theory for abstractness' sake. So I hoped to find some nice application or example which motivates the theory. My students are first year computer scientists. Preferably I would not have to introduce a lot of additional theory, but I have some room to discuss an interesting example.

If it helps: in previous sections the students have learned about regular languages, automata, Turing machines, P vs NP, graphs and graph algorithms.

Thank you for your ideas :)

Answer 1

[Update. This answer is giving applications of the Kleene recursion theorem, the fixed point theorem stating that for any computable function $f$, there is a program $e$ such that $e$ and $f(e)$ compute the same function. Evidently you are asking about the other Kleene fixed point theorem, however, and so this answer is not what you want.]

Quines. One dramatic application of the Kleene recursion fixed-point theorem is the existence of Quines. These are programs that produce their own code as output.

Any Turing complete programming language will admit such a Quine. To see this, let $f(e)$ be a program that writes $e$ as output. By the recursion theorem, there is a program $e$ such that $e$ and $f(e)$ compute the same function. So $e$ is a Quine, since $e$ will give $e$ as output, as this is what $f(e)$ does.

Universal algorithm. Another dramatic application of Kleene recursion is the baby version of the universal algorithm. Namely, there is a computer program $e$, which we can write down, such that it is consistent with PA (or ZFC, whatever foundational theory you want) such that $e$ writes any given finite string as output. To find such a program, let $f$ be the computable function that on input $p$, a program, searches for a proof in PA of a statement of the form "program $p$ does not output this specific string $s$". If it finds such a proof, then $f(p)$ gives output $s$ immediately and then halts.

By the recursion theorem, there is a program $e$ such that $e$ and $f(e)$ compute the same function (and provably so). So program $e$ searches for a proof that $e$ does not output string $s$, and when it finds such a proof, it outputs string $s$ and halts. It follows that you will not be able to prove that $e$ does not have any particular $s$ as output, since if you could actually prove this, then it wouldn't be true (for the smallest instance). So it is consistent with PA that it does have any given $s$ as output.

In other words, this is a program, which we can write down, whose behavior is not determined by the PA axioms — it can be anything at all.

For the grown up version of the universal algorithm, which exhibits the universal extension property, a theorem due to Woodin, with futher work by Enayat, Blanck, and myself, see my paper, The modal logic of arithmetic potentialism and the universal algorithm.

Computable numbers. There is another application to the theory of computable real numbers. In his famous 1936 paper, Turing had defined originally that a computable real number is one for which we have a computable procedure to enumerate the decimal digits. In computable analysis today, however, we define the computable numbers as those for which we can compute rational approximations to within any desired accuracy. The issue with Turing's definition is that if you have programs for $a$ and $b$, then you cannot produce a program to enumerate the digits of $a+b$. The problem is that you can't know in general whether there will be carries forcing you to flop over a long string of digits, and so if the numbers are looking like $a=0.343434\ldots$ and $b=0.65656565\ldots$, then $a+b$ will look like $0.9999\ldots$, but you won't know whether it is actually $1.000\ldots 0002\ldots$ or $0.9999\ldots 9992\ldots$ until you find out if there is a carry. But you will never know.

One can use the Kleene recursion theorem to prove that for any proposed program, there are computable reals $a$ and $b$ for which the program gets the wrong answer for $a+b$, as I explain in my post, Alan Turing on computable real numbers.

These are three applications of Kleene recursion that I give in my book Ten proofs of Gödel incompleteness, currently in preparation.

Answer 2

You can define the semantics of the Kleene star $r^*$ of a regular language $r$ as a least fixed point. The carrier set $L$ would be the set of all languages (over a fixed alphabet $\Sigma$), i.e. $\textrm{Pow}(\Sigma)$, the partial order would be subset/language inclusion. The least element in this order is $\emptyset$.

Then your function $f$ would map languages to languages as follows: $$f(s) ~{}={}~ s \cup \{\varepsilon\} \cup s \cdot r$$ That is, $f$ takes as input a language $s$ and adds to it the empty word $\varepsilon$ as well as $s$ concatenated with $r$.

Now if you start the Kleene iteration of $f$ from the least element $\emptyset$, you get \begin{align*} f^0(\emptyset) &~{}={}~ \emptyset\\ f(\emptyset) &~{}={}~ \emptyset \cup \{\varepsilon\} \cup \emptyset \cdot r ~{}={}~ \{\varepsilon\}\\ f^2(\emptyset) &~{}={}~ \{\varepsilon\} \cup \{\varepsilon\} \cup \{\varepsilon\} \cdot r ~{}={}~ \{\varepsilon\} \cup r\\ f^3(\{\varepsilon\} \cup r) &~{}={}~ \{\varepsilon\} \cup r \cup \{\varepsilon\} \cup \bigl(\{\varepsilon\} \cup r\bigr) \cdot r ~{}={}~ \{\varepsilon\} \cup r \cup r\cdot r\\ \vdots\\ f^n(\emptyset) &~{}={}~ \bigcup_{0 \leq k \leq n} r^k \end{align*} where $r^0 = \{\varepsilon\}$.