LOOP (programming language)

Template:Short description Template:Other uses Template:Use dmy dates LOOP is a simple register language designed to precisely capture the primitive recursive functions.Template:Sfn The language is derived from the counter-machine model.Template:Sfn Like the Counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers: inc x (increment), dec x (decrement: $\max (0,x-1)$), x = 0 (clear), and x = y (copy). The only control flow instruction is LOOP x: .... It causes the instructions within its scope to be repeated $x$ times.

In contrast to GOTO programs and WHILE programs, LOOP programs always terminate.Template:Sfn The running time is known in advance. Therefore, the set of functions computable by LOOP-programs is a proper subset of computable functions (and thus a subset of the computable by WHILE and GOTO program functions).Template:Sfn

The LOOP language admits several variants, distinguished by their set of basic instructions. Four such variants, L0 – L3, are distinguished in this article. Despite differences in syntactic convenience and loop-nesting depth, all variants compute exactly the primitive recursive functions.

At shallow nesting depths, the choice of basic instructions affects which functions are reachable. The simple functions are exactly the functions computable at depth 1 in L1; the Presburger-definable functions are exactly the functions computable at depth 1 in L3; the Kalmár elementary functions are exactly the functions computable at depth 2 in L1, L2, and a fortiori L3. From depth 3 onward all variants agree.

An example of a total computable function that is not LOOP-computable is the Ackermann function.Template:Sfn

History

The LOOP language was formulated in a 1967 paper by Albert R. Meyer and Dennis M. Ritchie. They showed the correspondence between the LOOP language and primitive recursive functions, proving that each primitive recursive function is LOOP-computable and vice versa.Template:Sfn

The language also was the topic of the unpublished PhD thesis of Ritchie.Template:SfnTemplate:SfnTemplate:Sfn

It was presented by Uwe Schöning, along with GOTO and WHILE.Template:Sfn

Definition

Several variants of the LOOP programming language have been defined, based on different sets of basic instructions. Despite these variations, they agree on the class of functions they compute: exactly the primitive recursive functions. However, when considering loop nesting depth Template:Mdashthat is, the number of nested LOOP constructs allowedTemplate:Mdash the choice of basic instructions affects the expressive power at shallow depths.

Four variants of the LOOP language are distinguished here:

• L0: Minsky (1967);Template:Sfn
• L1: Meyer & Ritchie (1967),Template:Sfn Tsichritzis (1970),Template:Sfn Machtey (1972),Template:Sfn Beck (1975),Template:Sfn Fachini & Maggiolo-Schettini (1979),Template:Sfn Goetze & Nehrlich (1980),Template:Sfn Calude (1988),Template:Sfn Schöning & Pruim (1998),Template:Sfn Tourlakis (2012),Template:Sfn Matos (2015);Template:Sfn
• L2: Tsichritzis (1971),Template:Sfn Beck (1975),Template:Sfn Kfoury & al (1982),Template:Sfn Odifreddi (1989),Template:Sfn Matos (2014);Template:Sfn
• L3: Cherniavsky (1976),Template:Sfn Cherniavsky & Kamin (1979),Template:Sfn Kfoury (1980),Template:Sfn Ibarra & Rosier (1983),Template:Sfn Handley & Wainer (1999).

In this presentation, the term "LOOP program" refers collectively to any of L0 – L3.

Syntax

A LOOP program consists of a sequence of instructions, which modify a finite number of registers, any of which may contain a non-negative integer.

If x and y are registers, define the following sets B_i of basic instructions:

• Template:Math
• Template:Math
• Template:Math
• Template:Math

For $0\le i\le 3$ we define the loop language Li as the smallest set of programs generated by the following rules:

1. Every instruction Template:Math is a program in Li.

2. If P and Q are in Li, then the sequential composition

P
Q

is in Li.

3. If Template:Math, then

LOOP x:
    P

is in Li.

Indentation determines block structure in a Python-like notation.

A LOOP program may be associated with a signature specifying input and output registers:

signature ::= 'def' program_name '(' input ')' '->' '(' output ')' ':'
input     ::= [ register (',' register)* ]
output    ::= register (',' register)*

Notes

• The signature is not part of the program.
• As Template:Code and Template:Code can be any lists of registers, in general P can compute several functions, depending on the chosen mapping.Template:Sfn So, multiple signatures can be associated to one single LOOP program.
• In this presentation an intended signature is placed before the program.

Semantics

Registers range over $\mathbb{N}=\{0,1,2,\dots \}$. Execution proceeds sequentially. A loop of the form LOOP x: ... executes its body exactly $x$ times, where $x$ is the value of the register at loop entry.

A LOOP program P is said to compute a function $f:{\mathbb{N}}^m\to {\mathbb{N}}^n$ when:

1. $𝚒𝚗𝚙𝚞𝚝$, an m-tuple, specifies $m$ registers which contain the arguments of $f(x_1,\dots ,x_m)$; the remaining registers contain $0$;
2. $𝚘𝚞𝚝𝚙𝚞𝚝$, an n-tuple, specifies $n$ registers;
3. after the execution of P the output registers contain $(y_1,\dots ,y_n)=f(x_1,\dots ,x_m)$.

Note

• When $𝚘𝚞𝚝𝚙𝚞𝚝$ specifies a single register, P defines a scalar-valued function; otherwise, P defines a vector-valued function.Template:SfnTemplate:SfnTemplate:Sfn

Definition

Template:Clear This definitionTemplate:SfnTemplate:SfnTemplate:Sfn agrees with the following:

A (vector-valued) function $f:{\mathbb{N}}^m\to {\mathbb{N}}^n$ is primitive recursive if it can be written as

$f(x_1,\dots ,x_m)=(f_1(x_1,\dots ,x_m),\dots ,f_n(x_1,\dots ,x_m))$

where each component $f_i:{\mathbb{N}}^m\to \mathbb{N}$ is a (scalar-valued) primitive recursive function.

Completing the set of basic instructions

As all four systems compute the primitive recursive functions:

• x = y is definable in L0 and in L2,
• dec x is definable in L0 and in L1.

Bootstrapping x = y

In L0 or L2 x = y can be implemented by the program

def copy(y) -> (x):
    LOOP y:
        inc x

We will write x = y in all languages, understanding that this instruction denotes x = copy(y) in L0 and in L2.
Wherever x = y appears in L0 or in L2 code, one has to add $1$ to the local loop depth.
The overall nesting depths are

""" Loop nesting: 1 (L0), 0 (L1) """

Bootstrapping dec x

The predecessor function

$x\dot{-}1=\max (0,x-1)=\{\begin{array}{cc}0& \text{if }x=0\\ x-1& \text{otherwise}\end{array}$

can be implemented by the programs

Template:Spacesin L0 def dec_L0(x) -> (x): LOOP x: x = 0 LOOP a: inc x inc a

Template:Spacesin L1Template:SfnTemplate:Sfn def dec_L1(x) -> (x): LOOP x: x = a inc a

We will write dec x in all languages, understanding that this instruction denotes dec_L0(x) in L0 and dec_L1(x) in L1.
Wherever dec x appears in L0 or in L1 code, one has to add $2$ respectively $1$ to the local loop depth.
The overall nesting depths are

""" Loop nesting: 2 (L0), 1 (L1), 0 (L2) """

Loop nesting

The central significance of the LOOP language lies in its stratification by maximum loop nesting depth. Writing Loop_k(L) for the class of functions computable by programs in variant L with at most k-nested LOOP constructs, the four variants are related by the following inclusion diagram:Template:Refn Template:Anchor

$\begin{array}{ccccc}& & 𝐋\mathrm{𝟑}& & \\ & \nearrow & & \nwarrow & \\ 𝐋\mathrm{𝟏}& & & & 𝐋\mathrm{𝟐}\\ & \nwarrow & & \nearrow & \\ & & 𝐋\mathrm{𝟎}& & \end{array}$

where an upward edge denotes that the upper variant has strictly more primitive instructions than the lower. L1 and L2 are incomparable: L1 has x = y but not dec x; L2 has dec x but not x = y; L3 has both; L0 has neither.

For nesting depth k < 2 this induces strict inclusions along the edges:

Template:Math

Template:Math

with Loop_k(L1) and Loop_k(L2) incomparable. The strict inclusions reflect the cost of simulating missing base instructions by extra loop nesting.
At depth 2 the classes collapse. In particular:

• At depth 1,

Loop₁(L1) = simple functions,Template:SfnTemplate:Sfn

Loop₁(L3) = Presburger functions:Template:Sfn

• At depth 2,

Loop₂(L1) = Loop₂(L2) = Kalmár elementary functions:Template:Sfn

The example programs below track loop nesting depth explicitly for each variant.

Macros as syntactic sugar

Let P and Q be LOOP programs.

Assume that Q is a program with $m$ input registers and $n$ output registers, computing a primitive recursive function

$(y_1,\dots ,y_n)=q(x_1,\dots ,x_m)$.

Suppose $m$ input registers of P supply the inputs $x_1,\dots ,x_m$, and we wish to use Q as a subroutine inside P.

Then the code of Q can be embedded ("macro-expanded") into P as follows:

1. rename all registers of Q to avoid collisions with registers of P;
2. copy the input values $x_1,\dots ,x_m$ from P into the input registers of Q;
3. initialize all auxiliary registers of Q to $0$;
4. execute the program Q;
5. copy the output values $y_1,\dots ,y_n$ from the output registers of Q into the designated registers of P.

This construction allows Q to be used as a subprogram of P, simulating an activation record in the sense required here.

Notes

• In P only the output registers are updated.
• This macro expansion does not alter the LOOP language. The notation is meant to improve the readability of the software and to facilitate the separate discussion of the inserted code. Template:Harvtxt goes further. His function calls enhance the language to augmented loop programs. Machtey allows calls to general recursive functions.

Example programs

Integer division by a constant

Integer division by a constant $k$ is a Presburger function that requires loop depth 1 in L1 and loop depth 2 in L2.

By convention, $\lfloor x/0\rfloor =0$.Template:Sfn $\lfloor x/k\rfloor$ can be computed by the LOOP program

def divk(x) -> (c1):
    """ Loop nesting: 2 (L0), 1 (L1), 2 (L2) """
    LOOP x:
        c0 = c1     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c1 = c2     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        ...         # ...        ...
        ck = c0     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        inc ck

def div4(x) -> (c1):
    """ Loop nesting: 2 (L0), 1 (L1), 2 (L2) """
    LOOP x:
        c0 = c1     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c1 = c2     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c2 = c3     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c3 = c4     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c4 = c0     # add to loop depth: 1 (L0), - (L1), 1 (L2)
        inc c4

Note

• The variables c0, c1, ..., ck form a cyclic shift chain, rotated one link to the left each iteration; ck is then incremented. Every $k$ iterations, the incremented value returns to c1, so c1 counts complete groups of $k$ iterations.

x modulo k

This is the (integer) remainder after division by a constant.

By convention, $x\mathrm{mod}0=x$.Template:Sfn For $k>0$:

$\begin{array}{cc}x\mathrm{mod}k& =x\dot{-}k\lfloor x/k\rfloor \\ & =\{\begin{array}{cc}x& \text{if }x<k,\\ (x-k)modk& \text{if }x\ge k.\end{array}\end{array}$

def modk(x) -> (r):
    """ Loop nesting: 2 (L0), 1 (L1) """
    # Step 1: Initialize the state ring
    inc c0

    # Step 2: Cycle the states x times
    LOOP x:
        # Shift the ring forward: 
        #  (c0, c1, c2, ..., c{k-1}) = (c{k-1}, c0, c1, ..., c{k-2})
        t0 = c0
        t1 = c1    # add to loop depth: 1 (L0), - (L1), 1 (L2)
        t2 = c2
        ...
        t{k-1} = c{k-1}

        c0 = t{k-1}
        c1 = t0    # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c2 = t1
        ...
        c{k-1} = t{k-2}

    # Step 3: Extract the final answer.
    LOOP c1: r = 1
    LOOP c2: r = 2
    ...
    LOOP c{k-1}: r = {k-1}

def mod5(x) -> (r):
    """ Loop nesting: 2 (L0), 1 (L1) """
    # Step 1: Initialize the state ring for k=5
    inc c0

    # Step 2: Cycle the states x times
    LOOP x:
        # Shift the ring forward: 
        #  (c0, c1, c2, c3, c4) = (c4, c0, c1, c2, c3)
        t0 = c0
        t1 = c1    # add to loop depth: 1 (L0), - (L1), 1 (L2)
        t2 = c2
        t3 = c3
        t4 = c4

        c0 = t4
        c1 = t0    # add to loop depth: 1 (L0), - (L1), 1 (L2)
        c2 = t1
        c3 = t2
        c4 = t3

    # Step 3: Extract the final answer.
    LOOP c1: r = 1
    LOOP c2: r = 2
    LOOP c3: r = 3
    LOOP c4: r = 4

Monus

This is the monus function (cutoff-subtraction).

$x\dot{-}y=\max (0,x-y)=\{\begin{array}{cc}x-y& \text{if }x\ge y\\ 0& \text{if }x<y\end{array}$

def monus(x, y) -> (x):
    """ Loop nesting: 3 (L0), 2 (L1), 1 (L2) """
    LOOP y:
        dec x     # add to loop depth: 2 (L0), 1 (L1)

The expanded L1 code is listed by Meyer & RitchieTemplate:Sfn and by Matos:Template:Sfn

def monus(x, y) -> (x):
    LOOP y:
        a = 0
        LOOP x:
            x = a
            inc a

Conditional selection

w

$\mathrm{w}(x,y)=\{\begin{array}{cc}x,& \text{if }y=0,\\ 0,& \text{if }y\ne 0.\end{array}$

def w(x, y) -> (x):
    """ Loop nesting: 1 (L0) """
    LOOP y:
        x = 0

Kronecker delta

The equality of two variables $x$ and $y$ is tested with the Kronecker delta

${\delta }_{xy}=\{\begin{array}{cc}0& \text{if }x\ne y\\ 1& \text{if }x=y\end{array}$

def eq(x, y) -> (result):
    """ Loop nesting: 3 (L0), 2 (L1), 1 (L2) """
    inc result          # assume equal

    test = monus(x, y)  # loop depth: 3 (L0), 2 (L1), 1 (L2)
    LOOP test:
        result = 0      # x > y

    test = monus(y, x)  # loop depth: 3 (L0), 2 (L1), 1 (L2)
    LOOP test:
        result = 0      # y > x

If ... then ... else ...

A conditional statement

IF x = y THEN execute P1 ELSE execute P2

can be translated to

test = eq(x, y)        # add to loop depth: 3 (L0), 2 (L1), 1 (L2)
LOOP test:
    P1
test = monus(1, test)  # add to loop depth: 3 (L0), 2 (L1), 1 (L2)
LOOP test:
    P2

Note

• The auxiliary register test must not appear in P1 or P2. This is guaranteed in macro-expanded code by renaming registers to avoid collisions.

x modulo y

This is the (integer) remainder.

By convention, $x\mathrm{mod}0=x$.Template:Sfn For $y>0$:

$\begin{array}{cc}x\mathrm{mod}y& =x\dot{-}y\lfloor x/y\rfloor \\ & =\{\begin{array}{cc}x& \text{if }x<y,\\ (x-y)mody& \text{if }x\ge y.\end{array}\end{array}$

def mod(x, y) -> (r):
    """
    Loop nesting: 3 (L0), 2 (L1), 2 (L2)
    Invariant: c = (y-1) - r
    """
    ym1 = 0
    LOOP y: inc ym1
    dec ym1                     # ADD TO LOOP DEPTH: 2 (L0), 1 (L1)
    c = 0
    LOOP ym1: inc c             # c = y-1 = initial countdown
    z0 = 1
    LOOP y: z0 = 0              # z0 = 1 iff y = 0
    LOOP x:
        nz = 0
        p = 0
        LOOP c: nz = 1; inc p   # nz = sg(c), p  = c
        dec p                   # p = c-1; ADD TO LOOP DEPTH: 2 (L0), 1 (L1)
        z = 1
        LOOP nz: z = 0          # z = 1 iff c = 0 (wrap)
        t = 0
        LOOP ym1: inc t
        LOOP nz: t = 0          # t = y-1 on wrap, else 0
        c = 0
        LOOP t: inc c           # c ⇐ y-1 on wrap,
        LOOP p: inc c           #     c-1 otherwise
        LOOP z: r = 0           # wrap: reset r
        LOOP nz: inc r          # step: increment r
    LOOP z0:                    # y = 0: r = x
        r = 0
        LOOP x: inc r

exp2

The function

${\exp }_2(x)=2^x$ can be implemented by the LOOP₂ program

def exp2(x) -> (y):
    """ Loop nesting: 2 (L0) """
    inc y
    LOOP x:
        LOOP y:
           inc y

Notes

• See also Meyer & Ritchie (1967a).
• ${\exp }_2$ grows exponentially, yet is computable by a LOOP₂ program.

Hyperoperators

Addition

Addition is the hyperoperation $H_1$.

$H_1(x,y)$ can be implemented by the LOOP₁ program

def add(x, y) -> (x):
    """ Loop nesting: 1 (L0) """
    LOOP y:
        inc x

Multiplication

Multiplication is the hyperoperation $H_2$:

$\begin{array}{ccc}x\cdot 0& =& 0\\ x\cdot (y+1)& =& (x\cdot y)+x\end{array}$

$H_2(x,y)$ can be computed by the LOOP₂ program

def mult(x, y) -> (z):
    """ Loop nesting: 2 (L0) """
    LOOP y:
        z = add(z, x)

More hyperoperators

Given a LOOP_i program for a hyperoperation $H_i$,
one can construct a LOOP_i+1 program for the next level.

$H_3$ is exponentiation:

$\begin{array}{ccc}{x}^0& =& 1\\ x^{y+1}& =& x^y\cdot x\end{array}$

$H_3(x,y)$ can be computed by the LOOP₃ program

def power(x, y) -> (z):
    """ Loop nesting: 3 (L0) """
    inc z
    LOOP y:
        z = mult(z, x)

This program expands toTemplate:Sfn

def power(x, y) -> (z):
    inc z
    LOOP y:
        temp = 0
        LOOP x:
            LOOP z:
                inc temp
        z = temp

Note

• Via superposition, the loop nesting of the exponentiation program reduces to 2 in L1 or L2, see below.

The steepest functions

Since the initial functions are all dominated by the successor function, iterations of it dominate all functions defined by iterations from the initial functions.Template:Sfn Let ${\mathrm{F}}_i$ be the (finite-level) fast-growing hierarchy of functions

$\begin{array}{ccc}{\mathrm{F}}_0(n)& =& n+1\\ {\mathrm{F}}_{m+1}(n)& =& {\mathrm{F}}_m^n(n)\end{array}$

where ${\mathrm{F}}_m^n$ is the n-th iterate of ${\mathrm{F}}_m$.

For fixed $k$, ${\mathrm{F}}_k(n)$ can be computed by the LOOP_k program

""" Loop nesting: k (L0) """
def F_k(n) -> (n):
    LOOP n:                  # loop depth: 1
        LOOP n:              # loop depth: 2
            ...              # ...
                LOOP n:      # loop depth: k
                    inc n    #

Note

• The diagonal function $D(n)={\mathrm{F}}_n(n)$ grows faster than ${\mathrm{F}}_k$ for every fixed $k$, and is a version of the Ackermann function. It is not LOOP-computable: any LOOP program has a fixed, finite nesting depth $k$, so it can only compute functions dominated by ${\mathrm{F}}_k$ for that particular $k$.

Simple functions

Several known classes of functions are characterised by finite superposition bases: closure under composition alone, with no looping or recursion. We write $⟨\dots ⟩$ for the closure of a set of functions under superposition.

Tsichritzis (1970)Template:SfnTemplate:Sfn defined simple functions as those obtainable by superposition from the basis

$⟨x+y,x\dot{-}1,\lfloor x/k\rfloor ,xmodk,\mathrm{w}(x,y)⟩$

where $k$ ranges over positive integer constants, and

$\mathrm{w}(x,y)=\{\begin{array}{cc}x& \text{if }y=0\\ 0& \text{if }y\ne 0\end{array}$

is the conditional selection function defined above.

All five basis operations are computable in Loop₁(L1):

• $x+y$: the addition;
• $x\dot{-}1$: the predecessor program dec_L1;
• $\lfloor x/k\rfloor$: the rotating counter programs;
• $xmodk$: the modulo-k programs;
• $\mathrm{w}(x,y)$: the w program.

Since all basis functions are Loop₁(L1) computable, and superposition does not increase nesting depth, the simple functions are exactly the Loop₁(L1) computable functions.

Presburger functions

Consider programs with loop nesting depth at most 1. The class of functions computable by L3 programs is the class of Presburger functions.Template:Sfn

The Presburger basis is obtained from the simple functions basis by replacing predecessor ($x\dot{-}1$) by monus ($x\dot{-}y$):

$⟨x+y,x\dot{-}y,\lfloor x/k\rfloor ,xmodk,\mathrm{w}(x,y)⟩$.

Note that $xmodk$ is redundant in the basis and is included only to make the parallel with the simple functions basis explicit.

The class of simple functions is a proper subclass of the Presburger functions:Template:Sfn

Loop₁(L1) $⊊$ Loop₁(L3) $=$ Presburger

Note that

• Loop₁(L1) falls short: in L1 $x\dot{-}y$ requires depth 2;
• Loop₁(L2) falls short: in L2 $\lfloor x/k\rfloor$ requires depth 2.

Kalmár elementary functions

Prunescu, Sauras-Altuzarra and Shunia (2026) provided a minimal superposition basis for Kalmár elementary functions:Template:Sfn

${ℰ}^3=⟨n+m,nmodm,2^n⟩$

Since these functions are Loop₂ computable in L1 as well as in L2 Template:Mdashcheck the examples aboveTemplate:Mdash Kalmár elementary functions can be computed by (loop-free) concatenation of Loop₂ programs in L1 or L2. Furthermore:

Loop₂(L1) = Loop₂(L2) = Loop₂(L3) = Kalmár elementary functions.

Example

The identity

$x^y=2^{(xy+x+1)y}mod(2^{xy+x+1}\dot{-}x)$Template:Sfn

allows $x^y$ to be computed by superposition from the substitution basis $⟨n+m,n\dot{-}m,nm,nmodm,2^n⟩$,Template:Refn
yielding a Loop₂ program in L1 or L2:

def power_by_superposition(x, y) -> (result):
    """ Loop nesting: 3 (L0), 2 (L1), 2 (L2) """
    base = mult(x, y)               # will become xy+x+1
    base = add(base, x)
    base = add(base, 1)             # base = xy+x+1
    e = mult(base, y)               # e = (xy+x+1)y
    dividend = exp2(e)
    divisor = exp2(base)
    divisor = monus(divisor, x)     # loop depth: 3 (L0), 2 (L1), 1 (L2)
    result = mod(dividend, divisor) # loop depth: 3 (L0), 2 (L1), 2 (L2)

Primitive recursive functions

The superposition basis approach introduced above extends to every level of the Grzegorczyk hierarchy.

Let $H_k$ denote the $k$-th hyperoperation ($H_1$ = addition, $H_2$ = multiplication, $H_3$ = exponentiation, $H_4$ = tetration, …).

Prunescu, Sauras-Altuzarra and Shunia (2026) proved that the Kalmár elementary functions are generated by three functions:

${ℰ}^3=⟨xmody,x+y,2^x⟩,$Template:Sfn

simplifying the base $⟨xmody,x+y,x\cdot y,2^x⟩$ of Mazzanti (2002)Template:Sfn by showing multiplication to be redundant.

Mazzanti's base theorem extends this to every level of the hierarchy: for $n\ge 3$,

${ℰ}^n=⟨mod,H_1,H_3,\dots ,H_n⟩,$Template:SfnTemplate:Sfn

and in the limit a base for all primitive recursive functions:

$𝐏𝐑=⟨mod,H_1,H_3,H_4,H_5,\dots ⟩.$

Multiplication $H_2$ appears at no level of the Mazzanti hierarchy. In particular, exponentiation $H_3$ is reachable at depth 2 directly from the basis $⟨xmody,x+y,2^x⟩$ — not via repeated multiplication — through the identity $x^y=2^{(xy+x+1)y}mod(2^{xy+x+1}\dot{-}x)$.

The bases translate directly into LOOP nesting depths via the example programs above, since superposition corresponds to loop-free concatenation of programs. At the elementary level, ${ℰ}^3={\text{Loop}}_2(𝐋\mathrm{𝟏})={\text{Loop}}_2(𝐋\mathrm{𝟐})$ (see above). From depth 3 onward the choice of variant is irrelevant, and for $n\ge 3$:

${\text{Loop}}_n(𝐋\mathrm{𝟎})={ℰ}^{n+1},$

one new loop per level. In particular tetration $H_4$ requires nesting depth exactly 3.

See also

• µ-recursive function
• primitive recursive function
• BlooP and FlooP

References

• Template:Cite conference

• Template:Cite web

• Template:Cite book

• Template:Cite journal

• Template:Cite journal

• Template:Cite book

• Template:Cite book

• Template:Cite journal

• Template:Cite journal

• Template:Cite proceedings

• Template:Cite journal

• Template:Cite AV media

• Template:Cite conference

• Template:Cite book

• Template:Cite journal

• Template:Cite journal

• Template:Cite web

• Template:Cite web

• Template:Cite journal

• Template:Cite report

• Template:Cite conference

• Template:Cite book

• Template:Cite book

• Template:Cite book

• Template:Cite journal

• Template:Cite book

• Template:Cite web

• Template:Cite book

• Template:Cite book

• Template:Cite book

• Template:Cite report

• Template:Cite book

• Template:Cite book

• Template:Cite journal

• Template:Cite journal

Bibliography

• Template:Cite journal

• Template:Cite journal

• Template:Cite journal

• Template:Cite journal

• Template:Cite journal

• Template:Cite journal

• Template:Cite journal

• Template:Cite book

• Template:Cite journal

External links

• Template:Cite web