General recursive function: Difference between revisions

Revision as of 14:56, 23 May 2023

Revision as of 16:13, 23 May 2023

Line 8:

==Definition==

The '''μ-recursive functions''' (or '''general recursive functions''') are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the [[μ operator|minimization operator {{mvar|μ}}]].

The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation){{Clarify}} is the class of [[primitive recursive functions]]. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the [[Ackermann function]] can be proven to be total recursive, and to be non-primitive.

Primitive or "basic" functions: