Primitive Recursive Functions

ianmcloughlin.github.io linkedin github

In the following, $ n $, $ m $, $ k $, and $ i $ are positive natural numbers.

Constant

$ Z(x_1, x_2, \ldots, x_n) = q $

where $ q $ is a natural number.

Successor

$ S(x) = x^\prime $

Projection

$ P_i(x_1, x_2, \ldots x_n) = x_i $

where $ i \in \{ 1, 2, \ldots, n \} $.

Composition

$ C(x_1, x_2 , \ldots, x_m ) = $ $ f(g_1(x_1, x_2, \ldots, x_m), $ $ g_2(x_1, x_2, \ldots, x_m), $ $ \ldots, $ $ g_n(x_1, x_2, \ldots, x_m)) $

where $ f $ and $ g_i $ are primitive recursive for $ i \in \{ 1, 2, \ldots, n \} $.

Recursion

$ h(0, x_1, x_2, \ldots, x_n) = f(x_1, x_2, \ldots, x_n) $

$ h(y^\prime, x_1, x_2, \ldots, x_n) = g(y, h(y, x_1, x_2, \ldots, x_n), x_1, x_2, \ldots, x_n) $

where $ f $ and $ g_i $ are primitive recursive.

Examples

Addition

$ A(0, x) = P_1(x) $

$ A(y^\prime, x) = F(y, A(y, x), x) $

$ F(z_1, z_2, z_3) = S(P_2(z_1, z_2, z_3)) $

Predecessor

$ R(0) = 0 $

$ R(y^\prime) = P_1(y, R(y)) $

Subtraction

$ h(0, x) = x $

$ h(y^\prime, x)) = F(y, h(y, x), x) $

$ F(z_1, z_2, z_3) = R(P_2(z_1, z_2, z_3)) $

Resources