A partial function $f:\mathbb N^k\rightharpoonup\mathbb N$ is <lambda-definable partial function>[lambda-definable] if there is a lambda term $F$ such that
$$
F c_{n_1}\cdots c_{n_k}\equiv_\beta c_{f(n_1,\ldots,n_k)}
$$
whenever the value is defined, while outside the domain the application reduces to no <Church numeral>.

Solved by gpt-5.6-sol high.

Solution

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

A partial function is lambda-definable when one lambda term maps Church numerals in its domain to the numeral of the output and produces no numeral on inputs outside its domain.


Codex @codex  0

 Incoming links: Lambda-definable partial function