LOOP (programming language)
≈ 30 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
LOOP is a simple register language designed to precisely capture the primitive recursive functions.[1] The language is derived from the counter-machine model.[2] Like the Counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers: inc x (increment), dec x (decrement: max(0,x−1)), x = 0 (clear), and x = y (copy). The only control flow instruction is LOOP x: .... It causes the instructions within its scope to be repeated x times.[3]
In contrast to GOTO programs and WHILE programs, LOOP programs always terminate.[4] 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).[5]
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.[6]
History
edit edit sourceThe 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.[7]
The language also was the topic of the unpublished PhD thesis of Ritchie.[8][9][10]
It was presented by Uwe Schöning, along with GOTO and WHILE.[11]
Definition
edit edit sourceSeveral 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);[12]
- L1: Meyer & Ritchie (1967),[7] Tsichritzis (1970),[13] Machtey (1972),[14] Beck (1975),[15] Fachini & Maggiolo-Schettini (1979),[16] Goetze & Nehrlich (1980),[17] Calude (1988),[18] Schöning & Pruim (1998),[19] Tourlakis (2012),[20] Matos (2015);[21]
- L2: Tsichritzis (1971),[22] Beck (1975),[15] Kfoury et al. (1982),[23] Odifreddi (1989),[24] Matos (2014);[25]
- L3: Cherniavsky (1976),[26] Cherniavsky & Kamin (1979),[27] Kfoury (1980),[28] Ibarra & Rosier (1983),[29] Handley & Wainer (1999).[30]
In this presentation, the term "LOOP program" refers collectively to any of L0 – L3.
Syntax
edit edit sourceA 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 Bi of basic instructions:
- B0 = {
x = 0,inc x} - B1 = B0 ∪ {
x = y} - B2 = B0 ∪ {
dec x} - B3 = B1 ∪ B2
For 0≤i≤3 we define the loop language Li as the smallest set of programs generated by the following rules:
1. Every instruction s ∈ Bi 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. 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
inputandoutputcan be any lists of registers, in general P can compute several functions, depending on the chosen mapping.[31] So, multiple signatures can be associated to one single LOOP program. - In this presentation an intended signature is placed before the program.
Semantics
edit edit sourceRegisters range over ℕ={0,1,2,…}. 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.[3]
A LOOP program P is said to compute a function f:ℕm→ℕn when:
- 𝚒𝚗𝚙𝚞𝚝, an m-tuple, specifies m registers which contain the arguments of f(x1,…,xm); the remaining registers contain 0;
- 𝚘𝚞𝚝𝚙𝚞𝚝, an n-tuple, specifies n registers;
- after the execution of P the output registers contain (y1,…,yn)=f(x1,…,xm).
- Note
- When 𝚘𝚞𝚝𝚙𝚞𝚝 specifies a single register, P defines a scalar-valued function; otherwise, P defines a vector-valued function.[32][33][34]
- Definition
A function f:ℕm→ℕn is primitive recursive iff it can be computed by a LOOP program.
This definition[32][19][35] agrees with the following:
- A (vector-valued) function f:ℕm→ℕn is primitive recursive if it can be written as
- f(x1,…,xm)=(f1(x1,…,xm),…,fn(x1,…,xm))
- where each component fi:ℕm→ℕ is a (scalar-valued) primitive recursive function.
Completing the set of basic instructions
edit edit sourceAs all four systems compute the primitive recursive functions:
x = yis definable in L0 and in L2,dec xis definable in L0 and in L1.
Bootstrapping x = y
edit edit source
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[36]
- """ Loop nesting: 1 (L0), 0 (L1) """
Bootstrapping dec x
edit edit source
The predecessor function[37]
- x−˙1=max(0,x−1)={0if x=0x−1otherwise
can be implemented by the programs
in L0
def dec_L0(x) -> (x): LOOP x: x = 0 LOOP a: inc x inc adef 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[36]
- """ Loop nesting: 2 (L0), 1 (L1), 0 (L2) """
Loop nesting
edit edit sourceThe central significance of the LOOP language lies in its stratification by maximum loop nesting depth. Writing Loopk(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:[40]
- 𝐋𝟑↗↖𝐋𝟏𝐋𝟐↖↗𝐋𝟎
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:
- Loopk(L0) ⊊ Loopk(L1) ⊊ Loopk(L3),
- Loopk(L0) ⊊ Loopk(L2) ⊊ Loopk(L3),
with Loopk(L1) and Loopk(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,
- Loop1(L1) = simple functions,[41][28][42]
- Loop1(L3) = Presburger functions:[26][43]
- At depth 2,
- Loop2(L1) = Loop2(L2) = Kalmár elementary functions:[44][45]
The example programs below track loop nesting depth explicitly for each variant.[36]
Macros as syntactic sugar
edit edit sourceLet 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
(y1,…,yn)=q(x1,…,xm).
Suppose m input registers of P supply the inputs x1,…,xm, 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;[46]
- copy the input values x1,…,xm from P into the input registers of Q;
- execute the program Q;
- copy the output values y1,…,yn 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
edit edit sourceInteger division by a constant
edit edit sourceInteger division by a constant k is a Presburger function that requires loop depth 1 in L1 and loop depth 2 in L2.
By convention, ⌊x/0⌋=0.[47] ⌊x/k⌋ can be computed by the LOOP program[36]
- 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: ⌊x/4⌋ |
|---|
| 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, ...,ckform a cyclic shift chain, rotated one link to the left each iteration;ckis then incremented. Every k iterations, the incremented value returns toc1, soc1counts complete groups of k iterations.
x modulo k
edit edit sourceThis is the (integer) remainder after division by a constant.
By convention, xmod0=x.[47] For k>0:
- xmodk=x−˙k⌊x/k⌋={xif x<k,(x−k)modkif x≥k.
| Example: xmod5 |
|---|
| 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
edit edit sourceThis is the monus function (cutoff-subtraction).
- x−˙y=max(0,x−y)={x−yif x≥y0if x<y
The expanded L1 code is listed by Meyer & Ritchie[48] and by Matos:[21]
- def monus(x, y) -> (x): LOOP y: a = 0 LOOP x: x = a inc a
Conditional selection
edit edit source- w
w(x,y)={x,if y=0,0,if y≠0.
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
- δxy={0if x≠y1if x=y
- If ... then ... else ...
- IF x = y THEN execute P1 ELSE execute P2
can be translated to[49]
- 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
testmust not appear inP1orP2. This is guaranteed in macro-expanded code by renaming registers to avoid collisions.
x modulo y
edit edit sourceThis is the (integer) remainder.
By convention, xmod0=x.[47] For y>0:
- xmody=x−˙y⌊x/y⌋={xif x<y,(x−y)modyif x≥y.
exp2
edit edit sourceThe function
- exp2(x)=2x can be implemented by the LOOP2 program[36]
- def exp2(x) -> (y): """ Loop nesting: 2 (L0) """ inc y LOOP x: LOOP y: inc y
- Notes
- See also Meyer & Ritchie (1967a).[50]
- exp2 grows exponentially, yet is computable by a LOOP2 program.
Hyperoperators
edit edit sourceAddition
edit edit sourceAddition is the hyperoperation H1.
H1(x,y) can be implemented by the LOOP1 program
- def add(x, y) -> (x): """ Loop nesting: 1 (L0) """ LOOP y: inc x
Multiplication
edit edit sourceMultiplication is the hyperoperation H2:
- x⋅0=0x⋅(y+1)=(x⋅y)+x
H2(x,y) can be computed by the LOOP2 program[51]
- def mult(x, y) -> (z): """ Loop nesting: 2 (L0) """ LOOP y: z = add(z, x)
More hyperoperators
edit edit sourceGiven a LOOPi program for a hyperoperation Hi,
one can construct a LOOPi+1 program for the next level.
H3 is exponentiation:
- x0=1xy+1=xy⋅x
H3(x,y) can be computed by the LOOP3 program[51]
- def power(x, y) -> (z): """ Loop nesting: 3 (L0) """ inc z LOOP y: z = mult(z, x)
This program expands to[52]
- 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
edit edit sourceSince the initial functions are all dominated by the successor function, iterations of it dominate all functions defined by iterations from the initial functions.[53] Let Fi be the (finite-level) fast-growing hierarchy of functions
- F0(n)=n+1Fm+1(n)=Fmn(n)
where Fmn is the n-th iterate of Fm.[54]
For fixed k, Fk(n) can be computed by the LOOPk 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)=Fn(n) grows faster than Fk 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 Fk for that particular k.
Simple functions
edit edit sourceSeveral known classes of functions are characterised by finite superposition bases: closure under composition alone, with no looping or recursion. We write ⟨…⟩ for the closure of a set of functions under superposition.
Tsichritzis (1970)[41][28] defined simple functions as those obtainable by superposition from the basis
- ⟨x+y,x−˙1,⌊x/k⌋,xmodk,w(x,y)⟩
where k ranges over positive integer constants, and
- w(x,y)={xif y=00if y≠0
is the conditional selection function defined above.
All five basis operations are computable in Loop1(L1):
- x+y: the addition;
- x−˙1: the predecessor program
dec_L1; - ⌊x/k⌋: the rotating counter programs;
- xmodk: the modulo-k programs;
- w(x,y): the w program.
Since all basis functions are Loop1(L1) computable, and superposition does not increase nesting depth, the simple functions are exactly the Loop1(L1) computable functions.[42]
Presburger functions
edit edit sourceConsider programs with loop nesting depth at most 1. The class of functions computable by L3 programs is the class of Presburger functions.[26]
The Presburger basis is obtained from the simple functions basis by replacing predecessor (x−˙1) by monus (x−˙y):
- ⟨x+y,x−˙y,⌊x/k⌋,xmodk,w(x,y)⟩.
Note that xmodk is redundant in the basis and is included only to make the parallel with the simple functions basis explicit.[55]
The class of simple functions is a proper subclass of the Presburger functions:[56]
- Loop1(L1) ⊊ Loop1(L3) = Presburger
Note that
- Loop1(L1) falls short: in L1 x−˙y requires depth 2;
- Loop1(L2) falls short: in L2 ⌊x/k⌋ requires depth 2.
Kalmár elementary functions
edit edit sourcePrunescu, Sauras-Altuzarra and Shunia (2026) provided a minimal superposition basis for Kalmár elementary functions:[44]
- ℰ3=⟨n+m,nmodm,2n⟩
Since these functions are Loop2 computable in L1 as well as in L2 —check the examples above— Kalmár elementary functions can be computed by (loop-free) concatenation of Loop2 programs in L1 or L2. Furthermore:[57]
- Loop2(L1) = Loop2(L2) = Loop2(L3) = Kalmár elementary functions.
- Example
The identity
- xy=2(xy+x+1)ymod(2xy+x+1−˙x)[44]
allows xy to be computed by superposition from the substitution basis ⟨n+m,n−˙m,nm,nmodm,2n⟩,[58]
yielding a Loop2 program in L1 or L2:[49]
- 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
edit edit sourceThe superposition basis approach introduced above extends to every level of the Grzegorczyk hierarchy.
Let Hk denote the k-th hyperoperation (H1 = addition, H2 = multiplication, H3 = exponentiation, H4 = tetration, …).
Prunescu, Sauras-Altuzarra and Shunia (2026) proved that the Kalmár elementary functions are generated by three functions:
- ℰ3=⟨xmody,x+y,2x⟩,[44]
simplifying the base ⟨xmody,x+y,x⋅y,2x⟩ of Mazzanti (2002)[59] by showing multiplication to be redundant.
Mazzanti's base theorem extends this to every level of the hierarchy: for n≥3,
and in the limit a base for all primitive recursive functions:
- 𝐏𝐑=⟨mod,H1,H3,H4,H5,…⟩.
Multiplication H2 appears at no level of the Mazzanti hierarchy. In particular, exponentiation H3 is reachable at depth 2 directly from the basis ⟨xmody,x+y,2x⟩ — not via repeated multiplication — through the identity xy=2(xy+x+1)ymod(2xy+x+1−˙x).[58]
The bases translate directly into LOOP nesting depths via the example programs above, since superposition corresponds to loop-free concatenation of programs. At the elementary level, ℰ3=Loop2(𝐋𝟏)=Loop2(𝐋𝟐) (see above). From depth 3 onward the choice of variant is irrelevant, and for n≥3:
- Loopn(𝐋𝟎)=ℰn+1,
one new loop per level. In particular tetration H4 requires nesting depth exactly 3.
See also
edit edit sourceNotes
edit edit source- ^ Enderton 2012.
- ^ Cutland 1980, p. 9.
- ^ a b 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.
- ^ Schöning 2008, p. 112.
- ^ a b Meyer & Ritchie 1967a.
- ^ Brock 2020.
- ^ Ritchie 1967.
- ^ Ritchie 1967a.
- ^ Schöning 2008, p. 105.
- ^ Minsky 1967, pp. 212–213, section 11.7.
- ^ Tsichritzis 1970, p. 729, Definition 1.
- ^ Machtey 1972.
- ^ a b Beck 1975.
- ^ Fachini & Maggiolo-Schettini 1979, pp. 59–60.
- ^ Goetze & Nehrlich 1980, p. 255.
- ^ Calude 1988, p. 384.
- ^ a b Schöning & Pruim 1998, p. 25.
- ^ Tourlakis 2012, p. 126, 2.2.0.8.
- ^ a b Matos 2015, p. 68.
- ^ Tsichritzis 1971.
- ^ Kfoury, Moll & Arbib 1982.
- ^ Odifreddi 1989, pp. 68, 70.
- ^ Matos 2014.
- ^ a b c Cherniavsky 1976.
- ^ Cherniavsky & Kamin 1979, p. 121.
- ^ a b c 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.
- ^ a b Fachini & Maggiolo-Schettini 1979.
- ^ Matos 2015.
- ^ PlanetMath.
- ^ Handley & Wainer 1999, pp. 278–279.
- ^ a b c d e The """ docstrings """ mention depths that improve 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
- ^ 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
- ^ a b Tsichritzis 1970.
- ^ a b Loop1(L2) falls short of simple functions: ⌊x/k⌋ requires depth 2 in L2.
- ^ Loop1(L1) falls short of Presburger: monus requires depth 2 in L1.
Loop1(L2) falls short of Presburger: ⌊x/k⌋ requires depth 2 in L2. - ^ a b c d Prunescu, Sauras-Altuzarra & Shunia 2026.
- ^ All three basis functions ⟨x+y,xmody,2x⟩ are Loop2 computable in both L1 and L2, so each Kalmár elementary function is reachable by loop-free concatenation of Loop2 programs in L1 or L2.
- ^ When Q is expanded inside a loop, its registers may still hold values from a previous pass.
- ^ a b c Prunescu, Sauras-Altuzarra & Shunia 2026, Introduction.
- ^ Meyer & Ritchie 1967a, p. 466, (2.2)..
- ^ a b Integer constants (
k) are shorthand for unused registers pre-initialised by repeatedinc: the constantkdenotes a fresh register set to k. An assignmentx = kof a literal constant abbreviatesx = 0followed by k occurrences ofinc x; both instructions lie in B0, 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
- ^ a b The expansion of assignments is explained above.
- ^ Tantau 2010, p. 148, 15-15.
- ^ Odifreddi 1999, p. 298.
- ^ Fm0(n)=nFmn+1(n)=Fm(Fmn(n))
- ^ xmodk is derivable from the remaining functions by superposition as x−˙⌊x/k⌋+⋯+⌊x/k⌋⏟k times
- ^ Ibarra & Rosier 1983, p. 198.
- ^ The inclusion Loop2(L1) ⊆ Kalmár elementary and Loop2(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 ℰ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.
- ^ a b Prunescu, Sauras-Altuzarra & Shunia (2026) derived n−˙m and nm from the basis ⟨n+m,nmodm,2n⟩. These functions can be added to the basis to simplify the computation.
- ^ a b Mazzanti 2002.
- ^ Kern 2026.
References
edit edit source- 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). 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 (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
edit edit source- Constable, Robert L.; Borodin, Allan B (1972). "Subrecursive programming languages, part I: Efficiency and program structure". Journal of the ACM. 19 (3): 526–568. doi:10.1145/321707.321721.
- Crolard, Tristan; Lacas, Samuel; Valarcher, Pierre (2006). "On the expressive power of the loop language". Nordic Journal of Computing. 13: 46–57.
- Crolard, Tristan; Polonowski, Emmanuel; Valarcher, Pierre (2009). "Extending the loop language with higher-order procedural variables". ACM Transactions on Computational Logic. 10 (4).
- Fachini, Emanuela; Maggiolo-Schettini, Andrea (1982). "Comparing Hierarchies of Primitive Recursive Sequence Functions". Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 28 (27–32): 431–445. doi:10.1002/malq.19820282705.
- Ibarra, Oscar H.; Leininger, Brian S. (1981). "Characterizations of Presburger Functions". SIAM Journal on Computing. 10 (1): 22–39. doi:10.1137/0210003.
- Minsky, Marvin (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
- Ritchie, Robert Wells (November 1965). "Classes of recursive functions based on Ackermann's function". Pacific Journal of Mathematics. 15 (3): 1027–1044. doi:10.2140/pjm.1965.15.1027.
- Rogers, Hartley Jr. (1987) [1967]. Theory of Recursive Functions and Effective Computability (Reprint ed.). MIT Press. ISBN 9780262680523.
- Shepherdson, J.C.; Sturgis, H.E. (1963). "Computability of Recursive Functions". Journal of the Association for Computing Machinery. 10 (2): 217–255. doi:10.1145/321160.321170.
External links
edit edit source- "Loop, Goto & While". Archived from the original on 9 June 2017.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374184925 under CC BY-SA 4.0; modifications have been made.