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.