LOOP (programming language)

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 proper subset of the functions computable by WHILE and GOTO programs).

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), Constable & Borodin (1972);
L1: Meyer & Ritchie (1967), Tsichritzis (1970), Machtey (1972), Beck (1975), Fachini & Maggiolo-Schettini (1979), Goetze & Nehrlich (1980), Calude (1988), Schöning & Pruim (1998), Enderton (2011), Tourlakis (2012), Matos (2015);
L2: Tsichritzis (1971), Beck (1975), Kfoury et 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 0 = {x = 0, inc x}$
$B 1 = B 0 \cup {x = y}$
$B 2 = B 0 \cup {dec x}$
$B 3 = B 1 \cup B 2$

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 \in 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 \in Li$ , then

LOOP x:
    P

is in Li.

Indentation determines block structure in a Python-like notation. For brevity, a short body may be written on the same line as its LOOP header, and consecutive instructions on one line are separated by semicolons.

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:

${\mathtt {input}}$ , an m-tuple, specifies $m$ registers which contain the arguments of $f(x_{1},\dots ,x_{m})$ ; the remaining registers contain $0$ ;
${\mathtt {output}}$ , an n-tuple, specifies $n$ registers;
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.

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

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.

For nesting depth k < 2 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. The strict inclusions reflect the cost of simulating missing base instructions by extra loop nesting.
At depth 2 the variants L1, L2 and L3 collapse; from depth 3 onward the choice of basic instructions ceases to matter and all four variants agree. 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.

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:

rename all registers of Q to avoid collisions with registers of P;
initialize all registers of Q to $0$ ;
copy the input values $x_{1},\ldots ,x_{m}$ from P into the input registers of Q;
execute the program Q;
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
    """
    LOOP y: inc ym1             # registers not listed as input hold 0
    dec ym1                     # ADD TO LOOP DEPTH: 2 (L0), 1 (L1)
    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

def F_k(n) -> (n):
    """ Loop nesting: k (L0) """
    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 (2026) 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 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}{\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 (2026) 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 of the Mazzanti hierarchy. In particular, exponentiation $H_{3}$ is reachable at depth 2 directly from the basis $\langle x{\bmod {y}},\;x+y,\;2^{x}\rangle$ — not via repeated multiplication — through the identity $x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\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, ${\mathcal {E}}^{3}={\text{Loop}}_{2}(\mathbf {L1} )={\text{Loop}}_{2}(\mathbf {L2} )$ (see above). 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.

Notes

↑ Meyer & Ritchie 1967a, p. 469, Theorem 7; Enderton 2011, p. 22.
↑ Cutland 1980, p. 9.
1 2 Changes of the content of register x during the execution of the loop do not affect the number of passes.
↑ Schöning 2008, p. 93.
↑ Schöning 2001, p. 122.
1 2 Kfoury (1980, p. 58, Theorem III.1). "That is, for loop-nestings of depth 3 or more, the computational power of loop programs becomes insensitive to the addition of primitive statements other than X ← 0 and X ← succ(X)."
↑ Schöning 2008, p. 112.
↑ Meyer & Ritchie 1967a, p. 469, Theorem 7.
↑ Brock 2020.
↑ Ritchie 1967.
↑ Ritchie 1967a.
↑ Schöning 2008, p. 105.
↑ Minsky 1967, pp. 212–213, section 11.7.
↑ Constable & Borodin 1972, p. 537.
↑ Meyer & Ritchie 1967a.
↑ Tsichritzis 1970, p. 729, Definition 1.
↑ Machtey 1972.
1 2 Beck 1975.
↑ Fachini & Maggiolo-Schettini 1979, pp. 59–60.
↑ Goetze & Nehrlich 1980, p. 255.
↑ Calude 1988, p. 384.
1 2 Schöning & Pruim 1998, p. 25.
↑ Enderton 2011, p. 21.
↑ Tourlakis 2012, p. 126, 2.2.0.8.
1 2 Matos 2015, p. 68.
↑ Tsichritzis 1971.
↑ Kfoury, Moll & Arbib 1982.
↑ Odifreddi 1989, pp. 68, 70.
↑ Matos 2014.
1 2 3 Cherniavsky 1976.
↑ Cherniavsky & Kamin 1979, p. 121.
1 2 3 Kfoury 1980.
↑ Ibarra & Rosier 1983.
↑ To L3 Handley & Wainer 1999, p. 278 added as basic the conditional if x = y then ... else ... fi.
↑ Goetze & Nehrlich 1980, p. 261.
1 2 Fachini & Maggiolo-Schettini 1979.
↑ Matos 2015.
↑ PlanetMath.
↑ Handley & Wainer 1999, pp. 278–279.
1 2 3 4 5 The """ docstrings """ give the loop nesting depth of the program shown, for each variant in which it improves upon all lower variants in the inclusion diagram; omitted variants inherit the minimum depth of their reachable predecessors.
↑
Implementation in Python:
```
x = 0 if x == 0 else x - 1
```
↑ Constable & Borodin 1972, p. 538, Phase I, items (1) and (2).
↑ Matos 2015, p. 68, Example 2.
↑ Tourlakis 2022, p. 157.
↑ This is a sub-diagram of the diagram shown in Kfoury 1980, p. 59, Theorem III.3
1 2 Tsichritzis 1970.
1 2 Loop₁(L2) falls short of simple functions: $\lfloor x/k\rfloor$ requires depth 2 in L2.
↑ Loop₁(L1) falls short of Presburger: monus requires depth 2 in L1.
Loop₁(L2) falls short of Presburger: $\left\lfloor x/k\right\rfloor$ requires depth 2 in L2.
1 2 3 4 Prunescu, Sauras-Altuzarra & Shunia 2026.
↑ All three basis functions $\langle x+y,\;x{\bmod {y}},\;2^{x}\rangle$ are Loop₂ computable in both L1 and L2, so each Kalmár elementary function is reachable by loop-free concatenation of Loop₂ programs in L1 or L2.
↑ When Q is expanded inside a loop, its registers may still hold values from a previous pass.
1 2 3 Prunescu, Sauras-Altuzarra & Shunia 2026, Introduction.
↑ Meyer & Ritchie 1967a, p. 466, (2.2)..
1 2 Integer constants (k) are shorthand for unused registers pre-initialised by repeated inc: the constant k denotes a fresh register set to $k$ . An assignment x = k of a literal constant abbreviates x = 0 followed by $k$ occurrences of inc x; both instructions lie in B₀, so such an assignment adds nothing to the loop depth in any variant.

↑ Meyer & Ritchie 1967a, p. 467–468:

def exp2(x) -> (y):
    inc y
    LOOP x:
        z = 0
        LOOP y:
            inc z
            inc z
        y = z

1 2 The expansion of assignments is explained above.
↑ Tantau 2010, p. 148, 15-15.
↑ Odifreddi 1999, p. 298.
↑ ${\begin{array}{rll}\operatorname {F} _{m}^{0}(n)&=&n\\\operatorname {F} _{m}^{n+1}(n)&=&\operatorname {F} _{m}(\operatorname {F} _{m}^{n}(n))\end{array}}$
↑ $x{\bmod {k}}$ is derivable from the remaining functions by superposition as $x\mathbin {\dot {-}} \underbrace {\lfloor x/k\rfloor +\cdots +\lfloor x/k\rfloor } _{k{\text{ times}}}$
↑ Ibarra & Rosier 1983, p. 198.
↑ The inclusion Loop₂(L1) ⊆ Kalmár elementary and Loop₂(L2) ⊆ Kalmár elementary both follow from the bounding lemma of Goetze & Nehrlich 1980, p. 257, Lemma 1: after two nested loops the register values are bounded by a function in ${\mathcal {E}}^{3}$ regardless of whether the base language is L1, L2 or L3, since the straight-line primitives affect only the constant factor in the growth bound, not the Grzegorczyk level.
1 2 Prunescu, Sauras-Altuzarra & Shunia (2026) derived $n\mathbin {\dot {-}} m$ and $nm$ from the basis $\langle n+m,\;n{\bmod {m}},\;2^{n}\rangle$ . These functions can be added to the basis to simplify the computation.
1 2 Mazzanti 2002.
↑ Kern 2026.

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". Journal of the ACM. 26 (1): 119–128. doi:10.1145/322108.322120.

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.

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

Enderton, Herbert B. (2011). Computability Theory: An Introduction to Recursion Theory. Academic Press. ISBN 978-0-12-384958-8.

Fachini, Emanuela; Maggiolo-Schettini, Andrea (1979). "A hierarchy of primitive recursive sequence functions" (PDF). RAIRO Informatique Théorique. 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. (April 2026). "A minimal substitution basis for the Kalmár elementary functions". Journal of Logic and Computation. 36 (3) exag010. arXiv:2505.23787. doi:10.1093/logcom/exag010.

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.). Heidelberg: Spektrum Akademischer Verlag. ISBN 3-8274-1099-1.

Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). Heidelberg: Spektrum Akademischer Verlag. ISBN 978-3-8274-1824-1. DNB 986529222.

Tantau, Till (12 February 2010). Vorlesungsskript Theoretische Informatik (PDF) (Report) (in German). Institut 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

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.

[FOOTNOTEMeyerRitchie1967a469Theorem_7Enderton201122-1] Meyer & Ritchie 1967a, p. 469, Theorem 7; Enderton 2011, p. 22.

[FOOTNOTECutland19809-2] Cutland 1980, p. 9.

[changes-3] 1 2 Changes of the content of register x during the execution of the loop do not affect the number of passes.

[FOOTNOTESchöning200893-4] Schöning 2008, p. 93.

[FOOTNOTESchöning2001122-5] Schöning 2001, p. 122.

[Kfoury_Theorem_III_1-6] 1 2 Kfoury (1980, p. 58, Theorem III.1). "That is, for loop-nestings of depth 3 or more, the computational power of loop programs becomes insensitive to the addition of primitive statements other than X ← 0 and X ← succ(X)."

[FOOTNOTESchöning2008112-7] Schöning 2008, p. 112.

[FOOTNOTEMeyerRitchie1967a469Theorem_7-8] Meyer & Ritchie 1967a, p. 469, Theorem 7.

[FOOTNOTEBrock2020-9] Brock 2020.

[FOOTNOTERitchie1967-10] Ritchie 1967.

[FOOTNOTERitchie1967a-11] Ritchie 1967a.

[FOOTNOTESchöning2008105-12] Schöning 2008, p. 105.

[FOOTNOTEMinsky1967212–213section_11.7-13] Minsky 1967, pp. 212–213, section 11.7.

[FOOTNOTEConstableBorodin1972537-14] Constable & Borodin 1972, p. 537.

[FOOTNOTEMeyerRitchie1967a-15] Meyer & Ritchie 1967a.

[FOOTNOTETsichritzis1970729Definition_1-16] Tsichritzis 1970, p. 729, Definition 1.

[FOOTNOTEMachtey1972-17] Machtey 1972.

[FOOTNOTEBeck1975-18] 1 2 Beck 1975.

[FOOTNOTEFachiniMaggiolo-Schettini197959–60-19] Fachini & Maggiolo-Schettini 1979, pp. 59–60.

[FOOTNOTEGoetzeNehrlich1980255-20] Goetze & Nehrlich 1980, p. 255.

[FOOTNOTECalude1988384-21] Calude 1988, p. 384.

[FOOTNOTESchöningPruim199825-22] 1 2 Schöning & Pruim 1998, p. 25.

[FOOTNOTEEnderton201121-23] Enderton 2011, p. 21.

[FOOTNOTETourlakis20121262.2.0.8-24] Tourlakis 2012, p. 126, 2.2.0.8.

[FOOTNOTEMatos201568-25] 1 2 Matos 2015, p. 68.

[FOOTNOTETsichritzis1971-26] Tsichritzis 1971.

[FOOTNOTEKfouryMollArbib1982-27] Kfoury, Moll & Arbib 1982.

[FOOTNOTEOdifreddi198968,_70-28] Odifreddi 1989, pp. 68, 70.

[FOOTNOTEMatos2014-29] Matos 2014.

[FOOTNOTECherniavsky1976-30] 1 2 3 Cherniavsky 1976.

[FOOTNOTECherniavskyKamin1979121-31] Cherniavsky & Kamin 1979, p. 121.

[FOOTNOTEKfoury1980-32] 1 2 3 Kfoury 1980.

[FOOTNOTEIbarraRosier1983-33] Ibarra & Rosier 1983.

[HandleyWainer-34] To L3 Handley & Wainer 1999, p. 278 added as basic the conditional if x = y then ... else ... fi.

[FOOTNOTEGoetzeNehrlich1980261-35] Goetze & Nehrlich 1980, p. 261.

[FOOTNOTEFachiniMaggiolo-Schettini1979-36] 1 2 Fachini & Maggiolo-Schettini 1979.

[FOOTNOTEMatos2015-37] Matos 2015.

[FOOTNOTEPlanetMath-38] PlanetMath.

[FOOTNOTEHandleyWainer1999278–279-39] Handley & Wainer 1999, pp. 278–279.

[docstrings-40] 1 2 3 4 5 The """ docstrings """ give the loop nesting depth of the program shown, for each variant in which it improves upon all lower variants in the inclusion diagram; omitted variants inherit the minimum depth of their reachable predecessors.

[41] Implementation in Python:
x = 0 if x == 0 else x - 1

[FOOTNOTEConstableBorodin1972538Phase_I,_items_(1)_and_(2)-42] Constable & Borodin 1972, p. 538, Phase I, items (1) and (2).

[FOOTNOTEMatos201568Example_2-43] Matos 2015, p. 68, Example 2.

[FOOTNOTETourlakis2022157-44] Tourlakis 2022, p. 157.

[45] This is a sub-diagram of the diagram shown in Kfoury 1980, p. 59, Theorem III.3

[FOOTNOTETsichritzis1970-46] 1 2 Tsichritzis 1970.

[L2FallsShort-47] 1 2 Loop₁(L2) falls short of simple functions: $\lfloor x/k\rfloor$ requires depth 2 in L2.

[L1L2FallShort-48] Loop₁(L1) falls short of Presburger: monus requires depth 2 in L1.
Loop₁(L2) falls short of Presburger: $\left\lfloor x/k\right\rfloor$ requires depth 2 in L2.

[FOOTNOTEPrunescuSauras-AltuzarraShunia2026-49] 1 2 3 4 Prunescu, Sauras-Altuzarra & Shunia 2026.

[50] All three basis functions $\langle x+y,\;x{\bmod {y}},\;2^{x}\rangle$ are Loop₂ computable in both L1 and L2, so each Kalmár elementary function is reachable by loop-free concatenation of Loop₂ programs in L1 or L2.

[init-51] When Q is expanded inside a loop, its registers may still hold values from a previous pass.

[FOOTNOTEPrunescuSauras-AltuzarraShunia2026Introduction-52] 1 2 3 Prunescu, Sauras-Altuzarra & Shunia 2026, Introduction.

[FOOTNOTEMeyerRitchie1967a466(2.2).-53] Meyer & Ritchie 1967a, p. 466, (2.2)..

[constants-54] 1 2 Integer constants (k) are shorthand for unused registers pre-initialised by repeated inc: the constant k denotes a fresh register set to $k$ . An assignment x = k of a literal constant abbreviates x = 0 followed by $k$ occurrences of inc x; both instructions lie in B₀, so such an assignment adds nothing to the loop depth in any variant.

[55] Meyer & Ritchie 1967a, p. 467–468:
def exp2(x) -> (y): inc y LOOP x: z = 0 LOOP y: inc z inc z y = z

[expansion-56] 1 2 The expansion of assignments is explained above.

[FOOTNOTETantau201014815-15-57] Tantau 2010, p. 148, 15-15.

[FOOTNOTEOdifreddi1999298-58] Odifreddi 1999, p. 298.

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

[60] $x{\bmod {k}}$ is derivable from the remaining functions by superposition as $x\mathbin {\dot {-}} \underbrace {\lfloor x/k\rfloor +\cdots +\lfloor x/k\rfloor } _{k{\text{ times}}}$

[FOOTNOTEIbarraRosier1983198-61] Ibarra & Rosier 1983, p. 198.

[62] The inclusion Loop₂(L1) ⊆ Kalmár elementary and Loop₂(L2) ⊆ Kalmár elementary both follow from the bounding lemma of Goetze & Nehrlich 1980, p. 257, Lemma 1: after two nested loops the register values are bounded by a function in ${\mathcal {E}}^{3}$ regardless of whether the base language is L1, L2 or L3, since the straight-line primitives affect only the constant factor in the growth bound, not the Grzegorczyk level.

[functions_added-63] 1 2 Prunescu, Sauras-Altuzarra & Shunia (2026) derived $n\mathbin {\dot {-}} m$ and $nm$ from the basis $\langle n+m,\;n{\bmod {m}},\;2^{n}\rangle$ . These functions can be added to the basis to simplify the computation.

[FOOTNOTEMazzanti2002-64] 1 2 Mazzanti 2002.

[FOOTNOTEKern2026-65] Kern 2026.

LOOP (programming language)

History

Definition

Syntax

Semantics

Completing the set of basic instructions

Bootstrapping x = y

Bootstrapping dec x

Loop nesting

Macros as syntactic sugar

Example programs

Integer division by a constant

x modulo k

Monus

Conditional selection

x modulo y

exp2

Hyperoperators

Addition

Multiplication

More hyperoperators

The steepest functions

Simple functions

Presburger functions

Kalmár elementary functions

Primitive recursive functions

See also

Notes

References

Bibliography

External links

Bootstrapping `x = y`

Bootstrapping `dec x`