# Composition is the only independent rule in Kleene's model of partial recursive functions

The following two theorems:

**Theorem 1:** The primitive recursive rule is reducible to repeated applications of specific compositions.
**Theorem 2:** The minimization (least-search) rule is reducible to repeated applications of specific compositions.

led to:

**Corollary:** Any computation defined by Kleene's model of partial recursive functions
can be done, according to Theorem 1 and Theorem 2, using the initial functions and the
repeated application of the composition rule.

The profs can be found in [1].

## References

[1] Gheorghe M. Stefan: "Composition is the only independent rule in Kleene's model of partial
recursive functions",