Primitive recursive function: Difference between revisions

Revision as of 16:38, 3 February 2024

Revision as of 08:18, 28 February 2024

Line 259:

== Elimination of parameters ==

{{expert needed|computer science|section|reason=properly explain the purpose of removing parameters (the text only explains *how* it is used, not *what for* - I guess in some Gödelian (un)computability proof)|date=November 2021}}

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.