Example. Semantics of recursive functions [dt-001U]

Consider the function \Phi \in (\mathbb {N}_\bot \rightarrow \mathbb {N}_\bot ) \rightarrow (\mathbb {N}_\bot \rightarrow \mathbb {N}_\bot ), given by: \Phi (f) = \lambda n.\ \text {if}\ n = 0\ \text {then}\ 1\ \text {else}\ n\cdot f(n-1) Looking at the first few elements of our Kleene chain, we get: \begin {array}{lcl} \Phi ^0(\bot ) & = & \lambda n.\ \bot \quad \text {(i.e. $\bot _{\mathbb {N}_\bot \rightarrow \mathbb {N}_\bot }$)}\\ \Phi ^1(\bot ) & = & \lambda n.\ \text {if}\ n = 0\ \text {then}\ 1\ \text {else}\ \bot \\ \Phi ^2(\bot ) & = & \lambda n.\ \text {if}\ n = 0\ \text {then}\ 1\ \text {else}\ n\cdot (\text {if}\ n - 1 = 0\ \text {then}\ 1\ \text {else}\ \bot )\\ \cdots \end {array} Continuing on, we see that the mth approximation \Phi ^m(\bot ) to \textbf {fix}(\Phi ) is the function that gives x! for all x up to m, and diverges (\bot ) for all other arguments. Hence the limit \textbf {fix}(\Phi ) is the factorial function on \mathbb {N}_\bot !