// Workers AI · dad joke modeWhat did LOOP say to its friend? You're in a cycle of friendship.

For other uses, see LOOP.

LOOP is a simple register language designed to precisely capture the primitive recursive functions. The language is derived from the counter-machine model. 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: $\operatorname {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. 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).

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.

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.

The language also was the topic of the unpublished PhD thesis of Ritchie.

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

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 —that is, the number of nested LOOP constructs allowed— the choice of basic instructions affects the expressive power at shallow depths.

Four variants of the LOOP language are distinguished here:

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

• B₀ = {x = 0, inc x}
• B₁ = B₀ ∪ {x = y}
• B₂ = B₀ ∪ { dec x }
• B₃ = B₁ ∪ B₂

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

1. Every instruction s ∈ B_i is a program in Li.

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

P
Q

is in Li.

3. If P ∈ Li, 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 input and output can be any lists of registers, in general P can compute several functions, depending on the chosen mapping. 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\colon \mathbb {N} ^{m}\to \mathbb {N} ^{n}$ when:

1. ${\mathtt {input}}$, an m-tuple, specifies $m$ registers which contain the arguments of $f(x_{1},\dots ,x_{m})$; the remaining registers contain $0$;
2. ${\mathtt {output}}$, 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 ${\mathtt {output}}$ specifies a single register, P defines a scalar-valued function; otherwise, P defines a vector-valued function.

Definition

A function $f\colon \mathbb {N} ^{m}\to \mathbb {N} ^{n}$ is primitive recursive iff it can be computed by a LOOP program.

This definition 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.

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:

${\begin{array}{ccccc}&&\mathbf {L3} &&\\&\nearrow &&\nwarrow &\\\mathbf {L1} &&&&\mathbf {L2} \\&\nwarrow &&\nearrow &\\&&\mathbf {L0} &&\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.

At each nesting depth k this induces strict inclusions along the edges:

Loop_k(L0) ⊊ Loop_k(L1) ⊊ Loop_k(L3),

Loop_k(L0) ⊊ Loop_k(L2) ⊊ Loop_k(L3),

with Loop_k(L1) and Loop_k(L2) incomparable for k = 1. The strict inclusions reflect the cost of simulating missing base instructions by extra loop nesting. In particular:

• At depth 1,

Loop₁(L1) = simple functions,

Loop₁(L3) = Presburger functions:

• At depth 2,

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

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

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\mathbin {\dot {-}} 1=\operatorname {max} (0,x-1)={\begin{cases}0&{\mbox{if }}x=0\\x-1&{\mbox{otherwise}}\end{cases}}$

can be implemented by the programs

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

in L1 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) """

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},\ldots ,y_{n})=q(x_{1},\ldots ,x_{m})$.

Suppose $m$ input registers of P supply the inputs $x_{1},\ldots ,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},\ldots ,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},\ldots ,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. Machtey (1972) 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, $\left\lfloor x/0\right\rfloor =0$. $\left\lfloor x/k\right\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

Example: $\left\lfloor x/4\right\rfloor$

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\operatorname {mod} 0=x$. For $k>0$:

${\begin{aligned}x\operatorname {mod} k&=x\mathbin {\dot {-}} k\left\lfloor x/k\right\rfloor \\[2mm]&={\begin{cases}x&{\text{if }}x<k,\\[2mm](x-k){\bmod {k}}&{\text{if }}x\geq k.\end{cases}}\end{aligned}}$

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}

Example: $x{\bmod {5}}$

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\mathbin {\dot {-}} y=\operatorname {max} (0,x-y)={\begin{cases}x-y&{\mbox{if }}x\geq y\\0&{\mbox{if }}x<y\end{cases}}$

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 & Ritchie and by Matos:

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

Conditional selection

w

$\operatorname {w} (x,y)={\begin{cases}x,&{\text{if }}y=0,\\0,&{\text{if }}y\neq 0.\end{cases}}$

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{cases}0&{\text{if }}x\neq y\\1&{\text{if }}x=y\end{cases}}$

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\operatorname {mod} 0=x$. For $y>0$:

${\begin{aligned}x\operatorname {mod} y&=x\mathbin {\dot {-}} y\left\lfloor x/y\right\rfloor \\[2mm]&={\begin{cases}x&{\text{if }}x<y,\\[2mm](x-y){\bmod {y}}&{\text{if }}x\geq y.\end{cases}}\end{aligned}}$

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

$\operatorname {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).
• $\operatorname {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}{ll}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}{ll}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 to

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. Let $\operatorname {F} _{i}$ be the (finite-level) fast-growing hierarchy of functions

${\begin{array}{lcl}\operatorname {F} _{0}(n)&=&n+1\\\operatorname {F} _{m+1}(n)&=&\operatorname {F} _{m}^{n}(n)\\\end{array}}$

where $\operatorname {F} _{m}^{n}$ is the n-th iterate of $\operatorname {F} _{m}$.

For fixed $k$, $\operatorname {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)=\operatorname {F} _{n}(n)$ grows faster than $\operatorname {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 $\operatorname {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 $\langle \ldots \rangle$ for the closure of a set of functions under superposition.

Tsichritzis (1970) defined simple functions as those obtainable by superposition from the basis

$\langle \,x+y,\;x\mathbin {\dot {-}} 1,\;\lfloor x/k\rfloor ,\;x{\bmod {k}},\;\operatorname {w} (x,y)\,\rangle$

where $k$ ranges over positive integer constants, and

$\operatorname {w} (x,y)={\begin{cases}x&{\text{if }}y=0\\0&{\text{if }}y\neq 0\end{cases}}$

is the conditional selection function defined above.

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

• $x+y$: the addition;
• $x\mathbin {\dot {-}} 1$: the predecessor program dec_L1;
• $\lfloor x/k\rfloor$: the rotating counter programs;
• $x{\bmod {k}}$: the modulo-k programs;
• $\operatorname {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.

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

$\langle \,x+y,\;x\mathbin {\dot {-}} y,\;\lfloor x/k\rfloor ,\;x{\bmod {k}},\;\operatorname {w} (x,y)\,\rangle$.

Note that $x{\bmod {k}}$ 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:

Loop₁(L1) $\subsetneq$ Loop₁(L3) $=$ Presburger

Note that

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

Kalmár elementary functions

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

${\mathcal {E}}^{3}=\langle \,n+m,\;n{\bmod {m}},\;2^{n}\,\rangle$

Since these functions are Loop₂ computable in L1 as well as in L2 —check the examples above— Kalmár elementary functions can be computed by (loop-free) concatenation of Loop₂ programs.

Example

The identity

$x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)$

allows $x^{y}$ to be computed by superposition from the substitution basis $\langle \,n+m,\;n\mathbin {\dot {-}} m,\;nm,\;n{\bmod {m}},\;2^{n}\,\rangle$,
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 (2025) proved that the Kalmár elementary functions are generated by three functions:

${\mathcal {E}}^{3}=\langle \,x{\bmod {y}},\;x+y,\;2^{x}\,\rangle ,$

simplifying the base $\langle x{\bmod {y}},\;x+y,\;x\cdot y,\;2^{x}\rangle$ of Mazzanti (2002) by showing multiplication to be redundant.

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

${\mathcal {E}}^{n}=\langle {\bmod {,}}\;H_{1},\;H_{3},\;\ldots ,\;H_{n}\rangle ,$

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

$\mathbf {PR} =\langle \,{\bmod {,}}\;H_{1},\;H_{3},\;H_{4},\;H_{5},\;\ldots \,\rangle .$

Multiplication $H_{2}$ appears at no level, being already generated at ${\mathcal {E}}^{3}$ by the Prunescu–Sauras-Altuzarra–Shunia base.

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, ${\mathcal {E}}^{3}={\text{Loop}}_{2}(\mathbf {L1} )={\text{Loop}}_{2}(\mathbf {L2} )$ (see above); in particular $H_{3}$ is computable at depth 2. From depth 3 onward the choice of variant is irrelevant, and for $n\geq 3$:

${\text{Loop}}_{n}(\mathbf {L0} )={\mathcal {E}}^{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

• Beck, H. (1975). "Zur Entscheidbarkeit der funktionalen Äquivalenz". In Brakhage, H. (ed.). Automata Theory and Formal Languages. Lecture Notes in Computer Science (in German). Vol. 33. Berlin, Heidelberg: Springer. pp. 127–133. doi:10.1007/3-540-07407-4_16.

• Brock, David C. (19 June 2020). "Discovering Dennis Ritchie's Lost Dissertation". CHM. Retrieved 30 August 2025.

• Calude, Cristian (1988). Theories of Computational Complexity. Annals of Discrete Mathematics. Vol. 35. North Holland Publishing Company. ISBN 9780080867755.

• Cherniavsky, John Charles (1976). "Simple Programs Realize Exactly Presburger Formulas". SIAM Journal on Computing. 5 (4): 666–677. doi:10.1137/0205045.

• Cherniavsky, John Charles; Kamin, Samuel Noah (1979). "A Complete and Consistent Hoare Axiomatics for a Simple Programming Language". Association for Computing Machinery. 26 (1): 119–128. doi:10.1145/322108.322120.

• Cutland, Nigel (1980). Computability: An Introduction to Recursive Function Theory (PDF). Cambridge University Press. ISBN 9780521223843. Retrieved 21 September 2025.

• Enderton, Herbert (2012). Computability Theory. Academic Press. ISBN 978-0-12-384958-8.

• Fachini, Emanuela; Maggiolo-Schettini, Andrea (1979). "A hierarchy of primitive recursive sequence functions" (PDF). R.A.I.R.O. - Informatique Théorique - Theoretical Informatics. 13 (1): 49–67. doi:10.1051/ita/1979130100491.

• Goetze, Bernhard; Nehrlich, Werner (1980). "The Structure of Loop Programs and Subrecursive Hierarchies". Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 26 (14–18): 255–278. doi:10.1002/malq.19800261407.

• Handley, W. G.; Wainer, S. S. (1999). "Complexity of Primitive Recursion". In Berger, Ulrich; Schwichtenberg, Helmut (eds.). Computational Logic. NATO ASI Subseries F: Computer and Systems Sciences. Vol. 165. Berlin; Heidelberg: Springer-Verlag. pp. 273–300. doi:10.1007/978-3-642-58622-4_8. ISBN 978-3-642-58622-4.

• Ibarra, Oscar H.; Rosier, Louis E. (1983). "Simple Programming Languages and Restricted Classes of Turing Machines". Theoretical Computer Science. 26 (1–2): 197–220. doi:10.1016/0304-3975(83)90085-3.

• Kern, Thomas (2026). Generating the Primitive Recursive Functions (video). Retrieved 5 July 2026 – via YouTube.

• Kfoury, Assaf J. (1980). "Analysis of Simple Programs Over Different Sets of Primitives". Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '80). New York, NY, USA: Association for Computing Machinery. pp. 56–61. doi:10.1145/567446.567452.

• Kfoury, Assaf J.; Moll, Robert N.; Arbib, Michael A. (1982). A Programming Approach to Computability. Springer, New York, NY. doi:10.1007/978-1-4612-5749-3. ISBN 978-1-4612-5751-6.

• Machtey, Michael (1972). "Augmented loop languages and classes of computable functions". Journal of Computer and System Sciences. 6 (6): 603–624. doi:10.1016/S0022-0000(72)80032-1.

• Mazzanti, Stefano (2002). "Plain Bases for Classes of Primitive Recursive Functions". Mathematical Logic Quarterly. 48 (1): 93–104. doi:10.1002/1521-3870(200201)48:1<93::AID-MALQ93>3.0.CO;2-8. ISSN 0942-5616.

• PlanetMath. "primitive recursive vector-valued function". Retrieved 19 May 2026.

• Matos, Armando B. (3 November 2014). "Closed form of primitive recursive functions: from imperative programs to mathematical expressions to functional programs" (PDF). Retrieved 20 August 2021.

• Matos, Armando B. (2015). "The efficiency of primitive recursive functions: A programmer's view". Theoretical Computer Science. 594: 65–81. doi:10.1016/j.tcs.2015.04.022.

• Meyer, Albert R.; Ritchie, Dennis MacAlistair (15 May 1967). Computational Complexity and Program Structure (PDF) (Report). IBM Research Report. IBM Research.

• Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967a). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. pp. 465–469. doi:10.1145/800196.806014.

• Minsky, Marvin Lee (1967). Computation: finite and infinite machines. Prentice Hall. doi:10.1017/S0008439500029350.

• Odifreddi, Piergiorgio (1989). Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Vol. I. Studies in Logic and the Foundations of Mathematics. Vol. 125. North-Holland. pp. xvii + 668. ISBN 0444872957.

• Odifreddi, Piergiorgio (1999). Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Vol. II. Studies in Logic and the Foundations of Mathematics. Vol. 143. Amsterdam: North-Holland. ISBN 978-0-444-50205-6. MR 1718169.

• Prunescu, Mihai; Sauras-Altuzarra, Lorenzo; Shunia, Joseph M. (24 May 2025). "A Minimal Substitution Basis for the Kalmar Elementary Functions". arXiv:2505.23787 [math.LO].

• Ritchie, Dennis MacAlistair (1967). Program structure and computational complexity (draft) (PDF).

• Ritchie, Dennis MacAlistair (1967a). "Program structure and computational complexity draft | 102790971 | Computer History Museum". www.computerhistory.org. Retrieved 14 July 2020.

• Schöning, Uwe; Pruim, R. (12 August 1998). "The Equivalence Problem for LOOP(1)- and LOOP(2)-Programs". Gems of Theoretical Computer Science. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-60322-8_4.

• Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4 ed.). London: Oxford University Press. ISBN 3-8274-1099-1.

• Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. ISBN 978-3-8274-1824-1. DNB 986529222.

• Tantau, Till (12 February 2010). Vorlesungsskript Theoretische Informatik (PDF) (Report) (in German). Insitut für Theoretische Informatik – Universität zu Lübeck. Retrieved 24 May 2026.

• Tourlakis, George J. (2012). Theory of Computation. Hoboken, New Jersey: John Wiley & Sons, Inc. ISBN 978-1-118-01478-3.

• Tourlakis, George (2022). Computability. Cham, Switzerland: Springer. ISBN 978-3-030-83202-5.

• Tsichritzis, Dennis C (1970). "The Equivalence Problem of Simple Programs". Journal of the ACM. 17 (4): 729–738. doi:10.1145/321607.321621.

• Tsichritzis, Dennis C (1971). "A note on comparison of subrecursive hierarchies". Information Processing Letters. 1 (2): 42–44. doi:10.1016/0020-0190(71)90002-0.

Bibliography

• Constable, Robert L.; Borodin, Allan B (1972). "Subrecursive programming languages, part I: Efficiency and program structure". Journal of the ACM. 19 (3): 526–568. doi:10.1145/321707.321721.

• Crolard, Tristan; Lacas, Samuel; Valarcher, Pierre (2006). "On the expressive power of the loop language". Nordic Journal of Computing. 13: 46–57.

• Crolard, Tristan; Polonowski, Emmanuel; Valarcher, Pierre (2009). "Extending the loop language with higher-order procedural variables". ACM Transactions on Computational Logic. 10 (4).

• Fachini, Emanuela; Maggiolo-Schettini, Andrea (1982). "Comparing Hierarchies of Primitive Recursive Sequence Functions". Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 28 (27–32): 431–445. doi:10.1002/malq.19820282705.

• Ibarra, Oscar H.; Leininger, Brian S. (1981). "Characterizations of Presburger Functions". SIAM Journal on Computing. 10 (1): 22–39. doi:10.1137/0210003.

• Minsky, Marvin (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.

• Ritchie, Robert Wells (November 1965). "Classes of recursive functions based on Ackermann's function". Pacific Journal of Mathematics. 15 (3): 1027–1044. doi:10.2140/pjm.1965.15.1027.

• Rogers, Hartley Jr. (1987) [1967]. Theory of Recursive Functions and Effective Computability (Reprint ed.). MIT Press. ISBN 9780262680523.

• Shepherdson, J.C.; Sturgis, H.E. (1963). "Computability of Recursive Functions". Journal of the Association for Computing Machinery. 10 (2): 217–255. doi:10.1145/321160.321170.

External links

• "Loop, Goto & While". Archived from the original on 9 June 2017.