Gödel's primitive recursive functions

Suppose ,
and
are Partial Numerical Functions.

The partial numerical function defined by

is called the composition of with

The partial numerical function defined by

is called the recursion of and

Definition

The class of primitive recursive functions is
the smallest class of partial functions containing all Basic Functions
that is closed under composition and recursion.

Theorem

Every primitive recursive function is Computable.