User:Marc Schroeder/sandbox

″

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 (like 'Increment', 'Clear', 'Copy', 'Decrement', ...) operate on the registers. 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).

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.

An example of a total computable function that is not LOOP computable is the Ackermann function.

Definition

Syntax

A LOOP program consists of

1. a finite number of registers, any of which may contain an arbitrary integer of $\mathbb {N} =\{0,1,2,...\}$;
2. a sequence of instructions as specified below.

The set of all LOOP programs L is defined by the following rules:

• Each of the arithmetic instructions, as well as the empty program, are elements of L.

• If $P$ ∈ L and x is a register, then the program

LOOP x:
    P

belongs to L.

• If $P$ ∈ L and $Q$ ∈ L, then the program

P
Q

belongs to L.

Formal definition

Compare with Python grammar

The specification below — in EBNF — uses whitespace to delimit control flow blocks (following the off-side rule).

• The symbol "::=" serves the same purpose as colon in Bison.
• Parentheses group.
• A trailing asterisk (*) indicates 0 or more repetitions.
• A trailing plus indicates 1 or more repetitions.

program ::= instruction*

instruction ::= 
    (arithmetic_instruction | loop_instruction) NEWLINE

arithmetic_instruction ::=
      inc_instruction        /* increment */
    | clr_instruction        /* clear     */
    | cpy_instruction        /* copy      */
    | dec_instruction        /* decrement */

inc_instruction ::= register "++"
clr_instruction ::= register "= 0"
cpy_instruction ::= register "=" register
dec_instruction ::= register "--"

loop_instruction ::= "loop" register ":" NEWLINE INDENT instruction+ DEDENT

register ::= char (char | digit)* 
char     ::= "A" | "B" | ... | "Z" | "_" | "a" | "b" | ... | "z"
digit    ::= "0" | "1" | ... | "9"

$m$ input registers are specified immediately above the program:

${\text{// INPUT ( }}\underbrace {\langle \operatorname {register} \rangle _{\scriptscriptstyle 1},\langle \operatorname {register} \rangle _{\scriptscriptstyle 2},\ldots ,\langle \operatorname {register} \rangle _{\scriptscriptstyle m}} _{m\geq 0{\text{ , repetitions allowed}}}{\text{ )}}$

$n$ output registers are specified immediately below the program:

${\text{// OUTPUT ( }}\underbrace {\langle \operatorname {register} \rangle _{\scriptscriptstyle 1},\langle \operatorname {register} \rangle _{\scriptscriptstyle 2},\ldots ,\langle \operatorname {register} \rangle _{\scriptscriptstyle n}} _{n\geq 1{\text{ , repetitions allowed}}}{\text{ )}}$

Semantics

Each register of a LOOP program may contain an arbitrary integer of $\mathbb {N} =\{0,1,2,...\}$.

The instructions are executed sequentially in the order in which they occur. The instruction LOOP x { ... } causes the included code to be executed $x$ times in succession, where $x$ denotes the contents of the register x upon entering the loop.

Definition

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

1. ${\mathtt {INPUT}}$, considered as an m-tuple, specifies $m$ registers which contain the arguments of $f(x_{1},\ldots ,x_{m})$; the remaining registers contain $0$;
2. ${\mathtt {OUTPUT}}$, considered as an n-tuple, specifies $n$ registers;
3. after the execution of P the output registers contain $(y_{1},\ldots ,y_{n})=f(x_{1},\ldots ,x_{m})$.

Remarks

• When ${\mathtt {OUTPUT}}$ specifies a single register the program defines a scalar-valued function. Otherwise the program defines a vector-valued function.

• Primitive recursive functions have the signature $f\colon \mathbb {N} ^{m}\rightarrow \mathbb {N}$, i.e. they map n arguments to a scalar value. LOOP-programs define exactly the primitive recursive functions. By consequence a LOOP-program executes a primitive recursive function iff ${\mathtt {OUTPUT}}$ specifies exactly one register.

• As any list of registers may be designated as input and output, in general a LOOP program can compute several functions, depending on the given mapping.

• It is natural to extend the notion of primitive recursiveness to vector-valued functions.

Definition: A (vector-valued) function is primitive recursive iff it can be computed by a LOOP program.

Remark on the choice of arithmetic instructions The LOOP language has been defined by many authors. The definitions do not agree on the arithmetic instructions. The minimum requirement is that it must be possible to increment registers and to set them to zero. This is achieved by the instructions x_i := x_i + 1, and either x_i := 0 or x_i := x_j.

From the instructions (1) and (2) the remaining instructions can be derived.

From the instructions (1) and (3) the remaining instructions can be derived.

No subroutines, but ...

Let P be any LOOP program.

Let $f\colon \mathbb {N} ^{m}\rightarrow \mathbb {N} ^{n}$ be a primitive recursive function. Then $f$ is computed by some LOOP program Q.

If P and Q do not share registers, Q can be inserted anywhere into P such that the programs do not affect each other.

The operation to rename the registers of Q is called alpha-conversion. This results in the program Q'.

Assume that P and Q' share no registers.

// INPUT (pi1, pi2, ..., pim)
Q'
// OUTPUT (po1, po2, ..., pon)

Wherever n registers of P need to be updated with the output of Q, given m registers of P as input, one can insert Q' into P and connect the input/output of Q' to the relevant registers of P. The resulting code is

pi1 = some_Qregister_1;
pi2 = some_Qregister_2;
...
pim = some_Qregister_m;
// clear all remaining registers of P'
P'
qo1 = po1;
qo2 = po2;
...
qom = po2;

(qo1, qo2, ..., qon) = P(qi1, qi2, ..., qim)

One can allow as an extra arithmetic instruction the instruction

(y1, y2, ..., yn) = P(x1, x2, ..., xm)

to indicate that the LOOP program has computed f on the side, and copied the output to the registers (y1, y2, ..., yn).

This is a short-hand notation to indicate that

Machtey (1971) added to the LOOP language the extra instruction Let P and Q be LOOP programs. can be patched into another loop program. The following workaround is possible.

Then P can be patched into a LOOP program Q, provided that

• (to avoid name collision) the local registers of P and m new registers (like tmpx1, tmpx2, ..., tmpxm) are not mentioned in Q;
• before the first line of P:
  • the registers x1, x2, ..., xm are backed up to tmpx1, tmpx2, ..., tmpxm respectively;
  • each register y1, y2, ..., yn is initialised to 0, if not mentioned in INPUT list;
  • each local register of P is initialised to 0;
• after the last line of P:
  • the registers x1, x2, ..., xm are restored from tmpx1, tmpx2, ..., tmpxm respectively.

This simulates the behaviour of an activation record, as far as needed here.

We write

...
(y1, y2, ..., yn) = S (x1, x2, ..., xm)
...

Example Programs

Addition

Addition is the hyperoperation function $\operatorname {H_{1}}$.

$\operatorname {H_{1}} (x,y)$ can be implemented by the LOOP program ADD( x, y )

# INPUT <x, y>
LOOP y:
    x = x + 1
# OUTPUT <x>

INPUT <x, y>
  ├─────────────┐
┌─┴───────┐    ╔╧╗
│x = x + 1│    ║y║
└─┬───────┘    ╚╤╝
  ├─────────────┘
OUTPUT <x>

          │
         ╔╧╗
         ║x║
         ╚╤╝

Assignment x = y without using type 3 instruction

If in the previous program — ADD — the register x is initialized to 0, the program copies the contents of register y to register x.

# INPUT <x, y>
x = 0
LOOP y:
    x = x + 1
# OUTPUT <x>

As the example shows the assignment instruction (x = y) can be removed from the list of arithmetic instructions without loss of expressive power.

Clearance x = 0 without using the type 2 instruction

{{{1}}}

Multiplication

Multiplication is the hyperoperation function $\operatorname {H_{2}}$.

$\operatorname {H_{2}} (x,y)$ can be computed by the LOOP program MULT( x, y )

# INPUT <x, y>
LOOP x:
    z = ADD( z, y )
# OUTPUT <z>

The program uses the ADD() program as a "convenience instruction". Expanded, the MULT program is a LOOP-program with two nested LOOP instructions. ADD counts for one.

More hyperoperators

Given a LOOP program for a hyperoperation function $\operatorname {H_{i}}$, one can construct a LOOP program for the next level.

$\operatorname {H_{3}} (x,y)$ for instance — exponentiation — can be implemented by the LOOP program POWER( x, y )

# INPUT <x, y>
z = z + 1
LOOP y:
    z = MULT( z, x )
# OUTPUT <z>

The exponentiation program, expanded, has three nested LOOP instructions.

Remark: To use MULT as a subroutine one has to take care of the clash of the variable z, which must have initial value 0 in MULT.

Predecessor

The predecessor function is defined as

$\operatorname {pred} (n)={\begin{cases}0&{\mbox{if }}n=0,\\n-1&{\mbox{otherwise}}\end{cases}}$.

$\operatorname {pred}$ is computed by the built-in arithmetic 'dec_instruction' . This instruction could be dropped, as $\operatorname {pred}$ can be derived from 'cpy_instruction' and 'inc_instruction' .

# INPUT (x)
LOOP x:
|   x = a
|   a++
# OUTPUT (x)

$\operatorname {pred}$ can also be derived from 'inc_instruction' and 'clr_instruction' .

# INPUT (x)
FirstTime++
LOOP x:
|   x++
|   LOOP FirstTime: 
|   |   FirstTime = 0
|   |   x = 0
# OUTPUT (x)

Remarks:

• The reason to keep 'dec_instruction' as an arithmetic instruction consists in the fact that $\operatorname {pred}$ cannot be programmed without wasting a LOOP in situations where a low LOOP nesting does matter.
• If OUTPUT is set to (FirstTime) instead of to (x) the program computes the function

$\operatorname {sgmin} (x)={\begin{cases}1&{\mbox{if }}x=0,\\0&{\mbox{otherwise}}\end{cases}}$.

INPUT <x>
  ├───────────────────┐
┌─┴───────┐1          │
│x = 0    │           │
└─┬───────┘           │
  ├─────────────┐     │
┌─┴───────┐2   ╔╧╗   ╔╧╗
│x = x + 1│    ║a║   ║x║
└─┬───────┘    ╚╤╝   ╚╤╝
  ├─────────────┘     │
┌─┴───────┐3          │
│a = a + 1│           │
└─┬───────┘           │
  ├───────────────────┘
OUTPUT <x>

This program can be used as a subroutine in other LOOP programs. The LOOP syntax can be extended with the following statement, equivalent to calling the above as a subroutine:

x0 := x1 ∸ 1

Remark: Again one has to mind the side effects, see above

Direct sum of 2x3 matrix and 2x2 matrix

The direct sum (denoted by $\oplus$) of any pair of matrices A of size 2 × 3 and B of size 2 × 2 is a matrix C of size (2 + 2) × (3 + 2), defined as

$\mathbf {A} \oplus \mathbf {B} ={\begin{bmatrix}\mathbf {A} &{\boldsymbol {0}}\\{\boldsymbol {0}}&\mathbf {B} \end{bmatrix}}={\begin{bmatrix}a_{11}&a_{12}&a_{13}&0&0\\a_{21}&a_{22}&a_{23}&0&0\\0&0&0&b_{11}&b_{12}\\0&0&0&b_{21}&b_{22}\end{bmatrix}}$

$\mathbf {C} =\mathbf {A} \oplus \mathbf {B}$ can be computed by an empty LOOP-program. The selection and the order of the input/output registers does the trick.

The 10-tuple < x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉ > is designated as INPUT.

The input registers are associated with the matrices $\mathbf {A}$ and $\mathbf {B}$ as follows:

$\mathbf {A} ={\begin{bmatrix}{\text{x}}_{0}\leftarrow a_{11}&{\text{x}}_{1}\leftarrow a_{12}&{\text{x}}_{2}\leftarrow a_{13}\\{\text{x}}_{3}\leftarrow a_{21}&{\text{x}}_{4}\leftarrow a_{22}&{\text{x}}_{5}\leftarrow a_{23}\end{bmatrix}}$

$\mathbf {B} ={\begin{bmatrix}{\text{x}}_{6}\leftarrow b_{11}&{\text{x}}_{7}\leftarrow b_{12}\\{\text{x}}_{8}\leftarrow b_{21}&{\text{x}}_{9}\leftarrow b_{22}\end{bmatrix}}$

The 20-tuple < x₀, x₁, x₂, x₁₀, x₁₁, x₃, x₄, x₅, x₁₂, x₁₃, x₁₄, x₁₅, x₁₆, x₆, x₇, x₁₇, x₁₈, x₁₉, x₈, x₉ > is designated as OUTPUT.

The output registers are associated with the matrix $\mathbf {C}$ as follows:

$\mathbf {C} ={\begin{bmatrix}{\text{x}}_{0}\leftarrow c_{11}&{\text{x}}_{1}\leftarrow c_{12}&{\text{x}}_{2}\leftarrow c_{13}&{\text{x}}_{10}\leftarrow c_{14}&{\text{x}}_{11}\leftarrow c_{15}\\{\text{x}}_{3}\leftarrow c_{21}&{\text{x}}_{4}\leftarrow c_{22}&{\text{x}}_{5}\leftarrow c_{23}&{\text{x}}_{12}\leftarrow c_{24}&{\text{x}}_{13}\leftarrow c_{25}\\{\text{x}}_{14}\leftarrow c_{31}&{\text{x}}_{15}\leftarrow c_{32}&{\text{x}}_{16}\leftarrow c_{33}&{\text{x}}_{6}\leftarrow c_{34}&{\text{x}}_{7}\leftarrow c_{35}\\{\text{x}}_{17}\leftarrow c_{41}&{\text{x}}_{18}\leftarrow c_{42}&{\text{x}}_{19}\leftarrow c_{43}&{\text{x}}_{8}\leftarrow c_{44}&{\text{x}}_{9}\leftarrow c_{45}\end{bmatrix}}$

Remarks:

• The function $\oplus$ is a vector-valued function.

• Recall that a primitive recursive function $f(x_{1},\ldots ,x_{n})$ maps its arguments to a scalar value. $f\colon (\mathbb {N} _{0})^{n}\rightarrow \mathbb {N} _{0}$. Considering that LOOP-programs execute exactly the primitive recursive functions, it is natural to extend this notion to vector-valued functions $f\colon (\mathbb {N} _{0})^{n}\rightarrow (\mathbb {N} _{0})^{k}$ by the following

Definition: A (vector-valued) function is primitive recursive iff it can be implemented by a LOOP program.

Cut-off subtraction

If in the 'addition' program above the second loop decrements x₀ instead of incrementing, the program computes the difference (cut off at 0) of the variables x₁ and x₂.

x0 := x1
LOOP x2 DO
  x0 := x0 ∸ 1
END

1.   x0 = x1
2.   LOOP x2 DO
3.           x0 = x0 ∸ 1
4.   END

# INPUT <X0, x1>
x0 = x1
LOOP x2:
    x0 = x0 ∸ 1
# OUTPUT <X0>

Remark

INPUT ⟨ x, y ⟩
LOOP y DO
  a := 0;
    LOOP x DO
      x := a;
      a := a + 1;
  END
END
OUTPUT ⟨ x ⟩

Like before we can extend the LOOP syntax with the statement:

x0 := x1 ∸ x2

If – then

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

$\operatorname {eq} (x,y)={\begin{cases}1&{\mbox{if }}x=y,\\0&{\mbox{otherwise}}\end{cases}}$.

This function can be computed by the LOOP program

# INPUT (x, y)
eq++
difference = x
LOOP y:
    difference--
LOOP difference:
    eq = 0
difference = y
LOOP x:
    difference--
LOOP difference:
    eq = 0
# OUTPUT (eq)

The control flow instruction ' if (x == y) then P' can then be simulated with

# do zero times or one time
LOOP eq:
    P

The steepest functions

Since the initial functions are all dominated by the successor function, iterations of it dominates all functions defined by iterations from the initial functions. Let $h_{i}$ be the (series of) functions

${\begin{array}{lcl}h_{0}(x)&=&x+1\\h_{n+1}(x)&=&h_{n}^{x}(x)\\\end{array}}$

where $h_{n}^{x}$ is the x-th iterate of $h_{n}$.

Consider any LOOP program P of length $l>0$. Then the function $h_{l-1}(x)$ dominates whatever function P might compute.

Also, on input $x$, P halts after the executions of at most $h_{l-1}(x)$ arithmetical imstructions. As LOOP programs have finite length, it follows that the generalized function $H(n,x)=h_{n}(x)$, an Ackermann function, cannot be computed by a LOOP program. This is a proof that the function $H(n,x)$ is not primitive recursive.

Example: the function $h_{4}(x)$ is computed by the following program of lenght 5:

# INPUT (x)
LOOP x:
|   LOOP x: 
|   |   LOOP x:
|   |   |   LOOP x: 
|   |   |   |   x++
# OUTPUT (x)

On input $x>1$ no other LOOP program of length at most 5 can output a bigger number.

If the loop nesting $k$ is taken into account, then a more advantageous bounding function can be established.

Let $c=\lceil {\frac {l}{k+1}}\rceil$.

Then $h_{k}^{c}$ dominates whatever function any LOOP program P of length $l$ and maximal loop nesting $k$ might compute. The idea is that the program is chopped up into c subprograms each of which races to the max. Each subprogram takes as input the output of the preceding subprogram.

Example: If $l=7$ and $k=2$ then $c=3$.

# INPUT (x)
LOOP x:
|   LOOP x: 
|   |   x++
LOOP x:
|   LOOP x: 
|   |   x++
LOOP x:
|   LOOP x: 
|   |   x++
# OUTPUT (x)

The structured program theorem

Consider the pseudocode listed in the strucured program article.

See Machtey 1972 and Calude 1988, p. 402, (Universal Language).

Marvin Minsky defined the following simple counter machine model, which is Turing complete. The instructions are

INC ( r ): INCrement the constents of register r
DEC ( r ): DECrement the constents of register r
JZ ( r, z ): IF register r contains Zero THEN Jump to instruction z ELSE continue in sequence.

A so-called Program machine consists of a finite sequence of n instructions. It can be simulated by a while-program of the form

p = 1
while p != 0:
    if p == 1:
        p = 2 
        if instruction 1 is of type JZ(r,z) and r == 0:
            p = z
        else:
            perform instruction 1

    if p == 2:
        p = 3
        if instruction 2 is of type JZ(r,z) and r == 0:
            p = z
        else:
            perform instruction 2

    (...)

    if p == n:
        p = 0
        if instruction n is of type JZ(r,z) and r == 0:
            p = z
        else:
            perform instruction n

This rewriting procedure actually proves the folk version of the structured program theorem by [Bohm Jacopini, 1966].

The LOOP-language does not have the while-instruction. The replacement of the while-instruction by the instruction LOOP t results in a LOOP-program which does the same as the while-program but stops after t iterations.

Meyer & Ritchie (1967) proved that ... xxx HIER VERDER 2

See also

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

Bibliography

• Axt, Paul (1966). "Iteration of relative primitive recursion". Mathematische Annalen. 167: 53–55. doi:10.1007/BF01361215.

• Axt, Paul (1970). "Iteration of primitive recursion". Journal of Symbolic Logic. 35 (3): 479. doi:10.1002/malq.19650110310.

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

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

• Cutland, Nigel (1980). Computability: An Introduction to Recursive Function Theory (PDF). Cambridge University Press. ISBN 0521223849. Retrieved 7 November 2023.

• Enderton, Herbert (2012). Computability Theory. Academic Press. doi:10.1145/1555746.1555750.

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

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

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

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

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

• Lipschutz, Seymour; Lipson, Marc (2017). Schaum's Outline of Linear Algebra (6 ed.). McGraw-Hill Education. ISBN 9781260011449.

• 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 2021-08-21.

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

• 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 (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. pp. 465–469. doi:10.1145/800196.806014.

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

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

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

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

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

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

External links

• Loop, Goto & While

Category:Computability theory