Primitive recursive function: Difference between revisions

Revision as of 08:18, 28 February 2024

Revision as of 08:24, 28 February 2024

Line 260:

== Elimination of parameters ==

The original primitive recursion schema was parameter-free. The primitive recursion schema as given may be replaced by one which makes use of fewer parameters. Let <math>w</math> be an elementary pairing function, and <math>\pi_1,\pi_2</math> be its projection functions for inversion.

Theorem: Any function constructible via the clauses of primitive recursion using the standard primitive recursion schema is constructible when the schema is replaced with the following.