Definitions & notation

The general recursive functions are the computable functions from fixed‐size lists of natural numbers into a natural number. (If their name strikes you as a poor fit for that concept, I agree, but it’s much too well established to attempt to change it.) The “type signature” of a GRF depends only on the length of the input list, making it the most significant property of a GRF; it’s called the function’s “arity”, and is notated with a superscript on the function’s name, tho it’s often omitted if the arity is clear without it.

The GRF’s are an extension to primitive recursive functions, which are best known for their roles in Gödel’s incompleteness theorems. Those functions are the ones that can be composed from these five operators:

  1. Nᵏ(n): numeric constant — when called with k arguments, evaluates to n, which must be a natural number. Also frequently denoted as “K”.
  2. S¹: successor — when called with the argument a, returns a+1. Also frequently denoted as “σ ”.
  3. Pᵏ(i): projection — when called with k arguments, returns the iᵗʰ one. Also frequently denoted as “π”.
  4. Rᵏ(g, h): primitive recursion — g must have arity k−1 and h arity k+1. When called with arguments x₁, x₂, ... xₖ where x₁=0, returns g(x₂, ... xₖ). When x₁≠0, returns h(x₁−1, v, x₂, ... xₖ) where v = Rᵏ(g, h)(x₁−1, x₂, ... xₖ). This reflects the common way of defining functions in number theory by specifying the case for x=0 independently and specifying the case for x > 0 in terms of the result for x−1. It’s also frequently denoted as “ρ”.
  5. Cᵏ(h, g₁, ..., gₘ): composition — This is the most complicated operator. h is called the “inner” function, and must have arity m. The g’s are “middle” functions, and each of them has arity k. The C operator generates the “outer” function, also of arity k. When the outer function is called with arguments x₁, ..., xₖ, it evaluates each middle function gᵣ (x₁, ..., xₖ) = vᵣ, and returns h(v₁, ..., vₘ).

The rationale behind that complicated definition of C is to support the mechanism of abstraction elimination. Using P(i) as a midfunc will cause it to evaluate to the iᵗʰ argument of the outer func, letting you re‐arrange arguments: e(x, y) ≝ f (y, x, y) gets represented by C(f, P²(2), P²(1), P²(2)). And when an argument is itself a function call, you can just nest compositions: e(x, y, z) ≝ f (z+1, y−x) gets represented by C(f, C(S, P³(3)), C(SUB, P³(2), P³(1))) where SUB is a subtraction function (SUB ≡ λa,b: a−b).

Someone being reminded of the non‐computability of the Halting Problem may notice that none of these operators can fail to terminate (or in mathematical terms, they all generate total functions), and so they obviously can’t represent all computable functions. To extend the primitive recursive functions to the general recursive functions, which are Turing‐complete, we add a sixth operator:

  1. Mᵏ(f ) or μᵏ(f ): minimization — f must have arity k+1. When Mᵏ(f ) is called with arguments x₁, ..., xₖ, it first calculates f (0, x₁, ..., xₖ), then f (1, x₁, ..., xₖ), then f (2, x₁, ..., xₖ), etc. until f (i, x₁, ..., xₖ) evaluates to 0, at which point it returns i. Or in math terms, it evaluates to min {i∈ℕ: f (i, x₁, ..., xₖ) = 0}.

If no natural number i results in f (i, x₁, ..., xₖ) returning 0, then the calculation of M(f ) loops forever. Because of this, expressions which don’t terminate are ubiquitous when dealing with GRF’s, so it’s convenient to have a placeholder value to represent that — here I use “∞”, but “⊥” (called “bottom”) is also commonly used.

The final bit of notation is that argument restrictions can be placed in a function’s argument list as shorthand for applying only when the restrictions are met. This most commonly happens with the R operator and a restriction of the form “a>0”, since that determines whether R(g, h) evaluates g or h. For example, f≡R²(S, P³(1)) can be described as: f (0, b) = b+1; f (a>0, b) = a−1

Note that although the syntax makes the operators (except S) look like higher‐order functions, they are generally not treated that way. Instead, they’re used as generators or constructors of GRF’s. Within a GRF expression they can’t be separated from their arguments, which must be numeric literals for N and P, and GRF’s of the proper arities for C, R, and M. You don’t get to obtain the iᵗʰ element of an arglist by calling C(P, <this‒calculates‒i>). (When analyzing GRF’s, we of course get to take the straitjacket off and have the operators’ arguments be variables, as seen in their definitions.)

In the literature, there are many minor variations in these definitions, because for nearly all theoretical purposes two definitions are close enough if one of them can easily emulate the other. So researchers will tweak the definitions slightly to a form that better suits their work, and it’s not an issue. In particular, the order of arguments varies because it’s obviously irrelevant to what computational tasks can and can not be accomplished. So, one might ask, why did I choose to have the R operator call its iteration function h with its v value (representing the value of the previous iteration) in the second argument, unnecessarily breaking up the xᵢ values? If I’d had it as the first argument, I could have partially applied it to h, and then both the call to the previous R(g, h) and the following call to h(v) would have both had the arglist (x₁−1, x₂, ... xₖ) and felt a lot more natural.

Well, that was how my GRF evaluator was originally written. But although the BBµ page doesn’t specify the argument order, it does give examples of R’s use in macros — which gave the wrong answers when I tried them out. I could have ignored this as “undocumented”, but in a busy beaver challenge, you are counting every last operator and the addition of trivial shims to alter argument order (or their removal when rendered unnecessary) actually matters. So, in deference to previous work I altered my evaluator to use the less natural convention that lets those macros work the way they’re written, although I remain unsure whether that was the right thing to do since I don’t know the motivation for the argument order required by the BBµ page’s macros.

Alright, so the six operators give us a way of representing any computable function ℕᵏ→ℕ (tho that’s far from obvious). But it’s bad for busy‐beavering because N⁰(anything) immediately gets you whatever natural number you want, so the BBµ page replaces Nᵏ with Zᵏ ≡ Nᵏ(0). Tho not explicitly stated, applying functions to arguments directly is apparently disallowed, as otherwise “S(Z⁰)” would be the size=2 champion with value 1, and instead we have to wait until size=3 to get value 1 with C(S, Z⁰).

[Top]