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",