Math 2.0

Mathematical logic and foundations Definition

General recursive function

Builds on Primitive recursive functionNatural numbers

Definition

A partial function f ⁣:ℕk⇀ℕf \colon \N^k \rightharpoonup \N is a function from a subset of ℕk\N^k to ℕ\N, where ℕ\N is the set of natural numbers. For a partial function g ⁣:ℕk+1⇀ℕg \colon \N^{k+1} \rightharpoonup \N, the minimisation μg ⁣:ℕk⇀ℕ\mu g \colon \N^k \rightharpoonup \N is defined as follows. The value μg(xˉ)\mu g(\bar x) is the least yy such that g(y,xˉ)=0g(y, \bar x) = 0 and g(z,xˉ)g(z, \bar x) is defined for all z<yz < y. If no such yy exists, then μg(xˉ)\mu g(\bar x) is undefined.

The class of partial recursive functions, or μ\mu-recursive functions, is the smallest class of partial functions ℕk⇀ℕ\N^k \rightharpoonup \N with these properties.

  1. It contains the zero function, the successor function and the projections, as for primitive recursive functions.
  2. It is closed under composition and primitive recursion, where a value is defined only when all values used to compute it are defined.
  3. It is closed under minimisation.

A general recursive function is a partial recursive function that is total, that is, defined at every point of ℕk\N^k.

Remarks

Example: let g(y,x)=x−˙y⋅yg(y, x) = x \mathbin{\dot-} y \cdot y, where a−˙b=max⁡(a−b,0)a \mathbin{\dot-} b = \max(a - b, 0). The function gg is primitive recursive, and g(y,x)=0g(y, x) = 0 exactly when y2≥xy^2 \ge x. So μg(x)=⌈x⌉\mu g(x) = \ceil{\sqrt x}, which is defined for all xx, and μg\mu g is general recursive.

Non-example: let g(y,x)=y+1g(y, x) = y + 1, which is never 00. Then μg\mu g is the empty function, which is partial recursive but not total, so it is not general recursive.

Terminology varies: some authors use "general recursive" for all partial recursive functions. Every primitive recursive function is general recursive, and the Ackermann function shows that the converse fails.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Natural numbers, object, no evidence levelNatural numbersobjectPrimitive recursive function, concept, no evidence levelPrimitive recursive f…conceptGeneral recursive function, definition, no evidence levelGeneral recursive fun…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Natural numbers object
  2. Primitive recursive function concept
  3. General recursive function definition

Further reading

  1. Web https://en.wikipedia.org/wiki/General_recursive_function
About this page
Tag4DQGSSWREK
URIm2://4DQGSSWREK
Kinddefinition
WritingW0 stub
MSC03D20
DefinesGeneral recursive function
UsesPrimitive recursive function, Natural numbers
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.