Partial recursive functions are a functional model of universal computation developed by Kleene, Gödel and Herbrand. Partial recursive functions are built from a set of basic functions — projection, zero and successor (which apply to tuples of integers) — using the operations of composition, primitive recursion and minimisation.

## Integers, projection, zero and successor

The integers can be represented in lambda calculus by the standard Church numerals.

The projection functions return one integer from a tuple — projection^{n}_{i}(`x _{1}`,

`x`,…,

_{2}`x`)=

_{n}`x`. This can be represented by the lambda expresssion λ

_{i}`x`

_{1}`x`…

_{2}`x`.

_{n}`x`.

_{i}
The zero functions return zero whatever their parameters — zero^{n}(`x _{1}`,

`x`,…,

_{2}`x`)=0. This can be represented by the lambda expression λ

_{n}`x`

_{1}`x`…

_{2}`x`.zero, where ‘zero’ is the Church numeral zero.

_{n}The successor function returns the successor of an integer — this can be represented by the successor function for Church numerals.

## Composition

The composition of the function f with the functions g_{1}, g_{2},… and g_{n}, applied to the tuple (`x _{1}`,

`x`,…,

_{2}`x`) is f(g

_{m}_{1}(

`x`,

_{1}`x`,…,

_{2}`x`),g

_{m}_{2}(

`x`,

_{1}`x`,…,

_{2}`x`),…,g

_{m}_{n}(

`x`,

_{1}`x`,…,

_{2}`x`)).

_{m}
This can be represented by the lambda expression λ`f``g _{1}`

`g`…

_{2}`g`

_{n}`x`

_{1}`x`…

_{2}`x`.

_{m}`f`(

`g`

_{1}`x`

_{1}`x`…

_{2}`x`)(

_{m}`g`

_{2}`x`

_{1}`x`…

_{2}`x`)…(

_{m}`g`

_{n}`x`

_{1}`x`…

_{2}`x`).

_{m}## Primitive rescursion

ρ^{n}(f,g) is the function h such that:

- h(
`x`,_{1}`x`,…,_{2}`x`,0) = f(_{n}`x`,_{1}`x`,…,_{2}`x`)_{n} - h(
`x`,_{1}`x`,…,_{2}`x`,_{n}`x`+1) = g(`x`,_{1}`x`,…,_{2}`x`,_{n}`x`,h(`x`,_{1}`x`,…,_{2}`x`,_{n}`x`))

This can be represented by the following lambda expression, which uses the fixed-point function Y, the predecessor function, and the test for zero ‘iszero’:

λ`f``g``x _{1}`

`x`…

_{2}`x`.Y(λ

_{n}`h`

`x`.iszero

`x`(

`f`

`x`

_{1}`x`…

_{2}`x`)(

_{n}`g`

`x`

_{1}`x`…

_{2}`x`(predecessor

_{n}`x`)(

`h`(predecessor

`x`))))

## Minimisation

μ(f)(`x _{1}`,

`x`,…,

_{2}`x`) returns the smallest

_{n}`x`such that f(

`x`,

_{1}`x`,…,

_{2}`x`,

_{n}`x`)=0 (note that such an

`x`may not exist).

This can be represented by the following lambda expression, which uses the fixed-point function Y, the successor function, and the test for zero ‘iszero’:

λ`f``x _{1}`

`x`…

_{2}`x`.(Y(λ

_{n}`h`

`x`.iszero(

`f`

`x`

_{1}`x`…

_{2}`x`

_{n}`x`)

`x`(

`h`(successor

`x`)))zero)