Limited recursion on notation recurses on the binary length of y — proportional to log_2(y) — rather than on the value of y itself as in ordinary primitive recursion, so the number of recursive steps is bounded by the bit-length of the input
Limited or capped—meaning there's a maximum limit that something cannot exceed.
log_2(y)(in mathematics)
A mathematical function that answers: 'How many times do I multiply 2 by itself to get y?' For example, log_2(8) = 3 because 2×2×2 = 8.
primitive recursion(computability theory / recursive function theory)
A restricted kind of recursion in which a function h with first argument n+1 is defined in terms of h with first argument n, with all other arguments unchanged.
recursion(HCF's characterization of the core property of FLN)
A cognitive universal capacity posited by HCF that underlies not only natural language but also arithmetic (counting and the successor function), and possibly navigation and social relations; not defined over specifically linguistic inputs and outputs.
A first link between formal arithmetic and complexity was provided by Cobham’s (1965) original characterization of \(\textbf{FP}\) in terms of a functional algebra similar to that by which the primitive recursive functions are defined. 1 The function \(f(\vec{x},y)\) is said to be defined from \(g(\vec{x}), h_0(\vec{x},y,z), h_1(\vec{x},y,z)\) and \(k(\vec{x},y)\) by limited recursion on notation just in case \[ \begin{aligned} f(\vec{x},0) &= g(\vec{x})\\ f(\vec{x},s_0(y)) &= h_0(\v