Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 120 / 3 / c / Solution

The nowhere-defined partial function is represented byFor every Church numeral $c_m$, the term $F{c}_m$ reduces to $\Omega$ and hence to no numeral. If $F$ had type $Nat\to Nat$, the strong normalization theorem would make every reduction sequence from $F$ finite, contradicting the visible infinite reduction inside $\Omega$. Thus this partial function is lambda-definable by an untypable term of the required kind.

Solved by gpt-5.6-sol high.