LOOP (programming language)

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, however, the choice of basic instructions affects which functions are reachable: with predecessor as a primitive (L2, L3), the Presburger-definable functions are computable at nesting depth 1, and the Kalmár elementary functions at depth 2. Without predecessor (L0, L1), neither correspondence can be established: not at depth 1 or 2, nor at any other nesting depth.

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 and Ritchie (1967), Tsichritzis (1970), Machtey (1972), Beck (1975), Fachini & Maggiolo-Schettini (1979), Goetze and Nehrlich (1980), Calude (1988), Schöning & Pruim (1998), Tourlakis (2012), Matos (2015);
• L2: Tsichritzis (1971), Beck (1975), Kfoury et al (1982), Odifreddi (1989), Matos (2014);
• L3: Cherniavsky (1976), Cherniavsky and Kamin (1979), Handley and 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₀ $\cup \;$ { x = y }
• B₂ = B₀ $\cup \;$ { dec x }
• B₃ = B₁ $\cup \;$ 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 ${\mathtt {input}}$ and ${\mathtt {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 a 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:

${\begin{aligned}{\text{Loop}}_{k}(\mathbf {L0} )&\subsetneq {\text{Loop}}_{k}(\mathbf {L1} )\subsetneq {\text{Loop}}_{k}(\mathbf {L3} ),\\[2pt]{\text{Loop}}_{k}(\mathbf {L0} )&\subsetneq {\text{Loop}}_{k}(\mathbf {L2} )\subsetneq {\text{Loop}}_{k}(\mathbf {L3} )\end{aligned}}$

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

• At depth 1, Loop₁(L3) = Presburger functions, while Loop₁(L1) or Loop₁(L2) fall strictly short: monus is Presburger-definable but requires depth 2 in L1. Integer division by a constant ($\left\lfloor x/k\right\rfloor$) is Presburger-definable but requires depth 2 in L2.
• At depth 2, Loop₂(L2) = Kalmár elementary functions, while Loop₂(L1) falls strictly short: x mod y is Kalmár elementary but requires depth 3 in L1.

The reason is that dec (predecessor) is a depth-0 primitive in L2 and L3 but must be simulated by a loop in L1, costing one extra nesting level wherever it is used. Adding a base instruction never increases loop nesting depth; it can only lower it. Predecessor is therefore an essential primitive: without it, neither the Presburger functions nor the Kalmár elementary functions are reachable at the expected depth.

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 2 in language 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

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.

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

Kronecker delta, if-then-else

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

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) -> (x):
    """ Loop nesting: 4 (L0), 3 (L1), 2 (L2) """
    LOOP x:
        b = y           # add to loop depth: 1 (L0), - (L1), 1 (L2)
        LOOP x: dec b   # add to loop depth: 2 (L0), 1 (L1)
        z = y           # add to loop depth: 1 (L0), - (L1), 1 (L2)
        LOOP b: z = 0
        LOOP z: dec x   # add to loop depth: 2 (L0), 1 (L1)

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).
• Note that $\operatorname {exp} _{2}$ grows exponentially, yet is computable by a LOOP₂ program.
• $\forall x,y\in \mathbb {N} :x^{y}\,\leq \,2y+2^{xy}$

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

• The loop nesting can be reduced to 2 in L3 by conversion to a time bounded (folk) structured program:

def power(x, y) -> (z):
    """ Loop nesting: 4 (L0), 3 (L1), 3 (L2), 2 (L3) """
    T = add(y, add(y, exp2(mult(x, y))))
    LOOP T:
        if p == 0             : inc z; yi = y;    p = 1
        if p == 1 and yi == 0 :                   p = 8 # final state
        if p == 1 and yi != 0 : temp = 0; xi = x; p = 3
        if p == 2             : dec yi;           p = 1
        if p == 3 and xi == 0 : z = temp;         p = 2
        if p == 3 and xi != 0 : zi = z;           p = 5
        if p == 4             : dec xi;           p = 3
        if p == 5 and zi == 0 :                   p = 4
        if p == 5 and zi != 0 :                   p = 7
        if p == 6             : dec zi;           p = 5
        if p == 7             : inc temp;         p = 6

The computation of $T=2y+2^{xy}$, an upper time bound sufficient to complete the simulation, is Loop₂.

The if lines are Loop₁ in L3:

    ...
    test = add(eq(p, 3), eq(xi, 0))             # line 8
    dec test
    LOOP test:
        z = temp     # add to loop depth: 1 (L0), 1 (L2)
        p = 2
    ...
    test = add(eq(p, 5), monus(1, eq(zi, 0)))   # line 12
    dec test
    LOOP test:
        p = 7
    ...

Note

• The loop nesting can be reduced to 2 even in 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$.

Presburger functions

Consider programs with loop nesting depth at most 1. Then the class of functions computable by L3 programs is the class of Presburger functions.

Kalmár elementary functions

Consider programs with loop nesting depth at most 2. Then the class of functions computable by L2 programs is the class of Kalmár-elementary functions. In particular, since the functions in the superposition basis $\langle n+m,\;n{\bmod {m}},\;2^{n}\rangle$ are Loop₂(L2) computable, every Kalmár elementary function can be computed by (loop-free) concatenation of Loop₂ L2 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 L2 or L3:

def power_by_superposition(x, y) -> (result):
    """ Loop nesting: 4 (L0), 3 (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: 4 (L0), 3 (L1), 2 (L2)

Notes

• The availability of dec x as a basic instruction is crucial for ensuring that the (Kalmár elementary) function $x{\bmod {y}}$ remains computable within Loop₂. Without predecessor, the computation of $x{\bmod {y}}$ requires nesting depth greater than 2 (4 in L0, 3 in L1). Allowing depth 3 would be overly powerful, since it enables computation of the non-elementary fast-growing function $\operatorname {F} _{3}$ (see above). Consequently, the Kalmár elementary class cannot be characterised by any fixed nesting depth in L1: the hierarchy jumps from strictly below ${\mathcal {E}}_{3}$ at depth 2 to strictly above ${\mathcal {E}}_{3}$ at depth 3, bypassing ${\mathcal {E}}_{3}$ entirely. Adding predecessor as a primitive restores the correspondence.
• From depth 3 onward, the correspondence Loop_i(L) = ${\mathcal {E}}_{i+1}$ holds independently of the choice of variant L1/L2/L3. Once LOOP_{i > 2} programs are expressed in flattened folk theorem form, the choice between L1 and L2 does not affect the nesting level of the program that depends only on the computation of the running time T.

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.

• Kfoury, A.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.

• 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.

• 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.

• 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 (JACM). 10 (2): 217–255. doi:10.1145/321160.321170.

External links

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