A Programming Formalism for PR^{∗}

George Tourlakis

October 9, 2002

1 Syntax and Semantics of Loop Programs

Loop programs were introduced by D. Ritchie and A. Meyer ([MR67]) as program-theoretic counterpart to the number theoretic introduction of the set of primitive recursive functions PR. This programming formalism among other things connected the definitional (or structural) complexity of primitive recursive functions with their (run time) computational complexity.

Loop programs are very similar to programs written in FORTRAN, but have a number of simplifications, notably they lack an unrestricted do-while instruction (equivalently, goto instruction). What they do have is

(1) Each program references (uses) a finite number of variables that we denote metamathematically by single letter names (upper or lower case is all right) with or without subscripts or primes.^{1}

(2) Instructions are of the following types (X, Y could be any variables below, including the case of two identical variables):

(i) X = 0

(ii) X = Y

(iii) X = X + 1

(iv) Loop X… end, where “…” represents syntactically valid instructions. The Loop part is matched or balanced by the end part.

Informally, the structure of loop programs can be defined by induction: Every instruction of type (i)–(iii) standing by itself is a loop program. If we already have two loop programs P and Q we can build two new ones. One is built by superposition or concatenation:

P
Q

∗Lecture notes for CS4111 and CS6113; Fall 2002

1The precise syntax of variables will be given shortly, but even after this fact we will continue using signs such as X, A, Z′, Y′′_{3}4 for variables—i.e., we will continue using metanotation.

The other is built by loop closure. For any variable X (that may or may not be in P), we form the new program:

Loop X P end

More formally we define the syntax of loop programs in BNF^{2} as follows (the notation ⟨name⟩ is reserved to name (“name”) syntactic categories, or, as we call these, nonterminals).

We start with the alphabet of symbols (terminals):

Σ = {v, 1, =, +, 0, Loop, end,; }  (1)

The grammar rules are^{3}

G1 (Variables):

⟨var⟩ → v1|⟨var⟩1

where “→” and “|” are metanotational symbols (part of the BNF descriptive notation,

not of Σ) and mean “is defined as” and “alternatively” respectively.

G2

⟨stmt⟩ →⟨var⟩ = 0
|⟨var⟩ = ⟨var⟩
| + ⟨var⟩
|Loop ⟨var⟩; ⟨prog⟩; end

G3

⟨prog⟩ →⟨stmt⟩
|⟨prog⟩; ⟨stmt⟩

Thus, G1 describes that a variable really is a string like v1 or v111 or, in general, v1^{n}—where 1^{n} is a string of n “1” (n ≥ 1).

G2 describes “single” statements. Just as in Algol descriptions (case of for-statements, blocks, etc.) we found it convenient to say that a whole construct such as “Loop X; P; end”— where P is some program—is a single statement. “;” acts a separator in our formal BNF, a symbol we normally suppress in informal discussions where we write loop programs vertically. Note that “+X” (where, as we have agreed, X is an informal variable name) is meant to stand for the informal “X = X + 1”. The former syntax makes the definition context free no matter how variables are defined, thus avoiding the well-known non-context free construct {w#w : w ∈ {0, 1}^{∗}}.^{4}

2Backus-Naur Form, that is, context free grammar notation that is used to describe (the “context free part” of)

Algol-like languages like Pascal, PL/1 or Algol itself.

3Familiarity with COSC2001 or equivalent is taken as a fact.

G3 describes programs as nonempty finite sequences of statements (or instructions). The second alternative in the definition makes the separator “;” left associative thus guiding any (reasonable) translation scheme to execute statements from left to right (or top to bottom in a vertical layout).^{5}

It is profitable to recast the above BNF in an ordinary inductive definition in the manner that, say, one defines the formulas of propositional or predicate calculus, or one defines PR.

In theoretical discussions about loop programs we will use the shorthand notation

v_{1}, v_{2}, …, v_{i}, …

to denote the sequence

v1, v11, …, v1^{i}, …

of variables. We will always denote loop programs by the letters P, Q, R,^{6} with or without primes and subscripts. We can now state:

Definition 1.1 The set of loop programs, L, is the smallest set of strings over Σ ((1), p.2) that includes all the initial strings^{7}

{v_{i} = 0 : i ≥ 1} ∪ {v_{i} = v_{j} : i ≥ 1 ∧ j ≥ 1} ∪ {+v_{i} : i ≥ 1}

and is closed under the following string-operations:

1. If P is in, then so is

Loop v_{i}; P; end

for any i ≥ 1.

2. If P and Q are in,^{8} then—for all i and j (both ≥ 1)—so are

(a) P; v_{i} = 0

(b) P; v_{i} = v_{j}

(c) P; +v_{i}

4With variables defined to be v1^{n}, a somewhat different context free grammar can effectively allow “X = X + 1”.

5It says that once we figured out that—in a string “P; I”—the P -part is a program, then if I is a statement we can proclaim that the whole thing is a program. This recognition has proceeded from left to right and correspondingly execution of these statements ought to proceed from left to right.

6These are informal meta-names entirely analogous to the meta-names X, Y, Z that we use for variables. In other contexts one acts analogously: For example, in logic one usually uses capital letters such as A, B, C—sometimes calligraphic, 𝒜 , ℬ, 𝒞 —to denote arbitrary formulas, p, q, r to denote Boolean variables and x, y, z, u, v, w to denote so-called “object variables”.

7Compare in other analogous contexts: Initial functions in PR; initial formulas (p, q, r, …, true, false) in Boolean logic.

8Of course, P and Q may—but don’t have to—name the same string (program). The same holds for v_{i} and v_{j}:

It is allowed to have i = j.

(d) P; Loop v_{j}; Q; end ■

The semantics of loop programs describe what the execution of such a program does to the values (or “contents”) of its list, or vector, of variables. Throughout this note will use the notations “[a_{1}, a_{2}, …, a_{r}]”, “a_{1}, a_{2}, …, a_{r}” and “a⃗_{r}” for vectors interchangeably. The first notation is typographically clearer in some contexts as—via bracketing—it emphasizes that we view the sequence a_{1}, …, a_{r} as one object; for example, as output of a vector-valued function.^{9}

Definition 1.2 (Loop Program Semantics) Let the sequence v_{1}, …, v_{n} include all the variables referenced in a program P. We denote by λv⃗_{n}.P (v⃗_{n}) the vector-valued function from ℕ^{n} → ℕ^{n} defined by induction on the definition of P (using 1.1) as follows:

For all (values of) v_{1}, …, v_{n}, if P is

1. v_{i} = 0: Then P (v⃗_{n}) = [v_{1}, …, v_{i−1}, 0, v_{i+1}, …, v_{n}], for 1 ≤ i ≤ n.

2. v_{i} = v_{j}: Then P (v⃗_{n}) = [v_{1}, …, v_{i−1}, v_{j}, v_{i+1}, …, v_{n}], for 1 ≤ i ≤ n.

3. +v_{i}: Then P (v⃗_{n}) = [v_{1}, …, v_{i−1}, v_{i} + 1, v_{i+1}, …, v_{n}], for 1 ≤ i ≤ n.

4. Loop v_{k}; Q; end: Then P (v⃗_{n}) = Q^{v_{k}}(v⃗_{n}),^{10} where the vector valued iteration Q^{a}(v⃗_{n}) is defined by

\begin{aligned}Q^{0}(v⃗_{n}) & = [v_{1}, …, v_{n}] \\ Q^{a+1}(v⃗_{n}) & = Q(Q^{a}(v⃗_{n})) \end{aligned}  (2)

5. R; S, where S is a program that consists of a single instruction, one among 1–4 above:

Then

P (v_{1}, …, v_{n}) = S(R(v_{1}, …, v_{n}))  (3)
■

Case 4 above warrants a comment. It says that if v_{k} = a then the effect of Loop v_{k}; Q; end is the same as that of the program

Q; Q; ⋯; Q

a copies of Q

regardless of what may be happening to v_{k} inside Q. That is, if v_{k} is changed by Q this does not affect the number of times the loop executes; this depends only on the value a of v_{k} just prior to entering the loop. In particular, if a = 0 the loop is skipped.

Note that the vector primitive recursion (2) above is shorthand for an ordinary simultaneous recursion of number theoretic functions (right field ℕ). Indeed, renaming Q^{a}(v⃗_{n}) as g(a, v⃗_{n}) and setting

g(a, v⃗_{n}) = [g_{1}(a, v⃗_{n}), …, g_{n}(a, v⃗_{n})]

and

Q(v⃗_{n}) = [q_{1}(a, v⃗_{n}), …, q_{n}(a, v⃗_{n})]

9In which case it is clearer to write, say, “f(a) = [c, d, e, f]” rather than “f(a) = c, d, e, f”.

10In the case of functions, the notation f^{k} means composition k times; not exponentiation.

we have for i = 1, …, n:

\begin{aligned}g_{i}(0, v⃗_{n}) & = v_{i} \\ g_{i}(a + 1, v⃗_{n}) & = q_{i}(g_{1}(a, v⃗_{n}), …, g_{n}(a, v⃗_{n})) \end{aligned}  (2′)

Thus, if all the vector-components of the Q-function—the λv⃗_{n}.q_{i}(v⃗_{n}) above—are in PR, then so are all the λav⃗_{n}.g_{i}(a, v⃗_{n}), and therefore all the components of λv⃗_{n}.P (v⃗_{n}), namely the λv⃗_{n}.p_{i}(v⃗_{n}), because P (v⃗_{n}) = Q^{v_{k}}(v⃗_{n}) = g(v_{k}, v⃗_{n})—hence p_{i}(v⃗_{n}) = g_{i}(v_{k}, v⃗_{n}).

Similar comments apply to (3) above: Let us write p for the vector valued function λv⃗_{n}.P (v⃗_{n}) and similarly r for λv⃗_{n}.R(v⃗_{n}) and s for λv⃗_{n}.S(v⃗_{n}). Then p = [p_{1}, …, p_{n}], q = [q_{1}, …, q_{n}] and s = [s_{1}, …, s_{n}]. Thus each p_{i}, q_{i}, s_{i} is a number theoretic function of n variables (i.e., from ℕ^{n} to ℕ). Clearly, p_{i} = s_{i} ∘ [r_{1}, …, r_{n}], where “∘” denotes function composition. Thus, if all the r_{i} and all the s_{i} are in PR, then so are all the p_{i} functions.

We have done all the work that allows us to now state

Theorem 1.3 For any loop program P whose variables are among v⃗_{n}, each of the functions λv⃗_{n}.u_{i}^{n}(P (v⃗_{n}))—for i = 1, …, n—is in PR.

Proof Induction of programs P. If P corresponds to 1–3 in Definition 1.2, then each of λv⃗_{n}.u_{i}^{n}(P (v⃗_{n})) is initial.

For case 4, we are done by the I.H. (induction hypothesis) on P and earlier remarks. For case 5, if S is of type 1-3, then we are done by (3) and the I.H. on R. If S is of type 4,

then we are done by (3) and the I.H. on R and Q. ■

2 PR vs. L

We next define what it means for a program P —whose list of variables is v_{1}, …, v_{n}—to compute a number theoretic function: First we decide which ones among the v⃗_{n} we want to be the input variables; say^{11}

v_{1}, …, v_{r}  (4)

We also decide on one output variable; say, v_{k}.

We assume that the agent that executes a loop program, implicitly—i.e., not via instructions that are contained in the program—initializes to 0 all the variables other than those in the list (4) and then starts to execute P.^{12} At termination^{13} we read off what v_{k} holds. This correspondence, v⃗_{r} ↦ v_{k}, induced by the execution of P is the function that P computes with input v⃗_{r} and output v_{k}. In symbols P v⃗_{r} ; v_{k}. This informal description is captured as follows:

Definition 2.1 For a program P whose variable list is v⃗_{n} we define the symbol P v⃗_{r} ; v_{k}, where 1 ≤ r, k ≤ n, to mean

λv⃗_{r}.u_{k}^{n}(P (v⃗_{r}, \underbrace{0, …, 0}_{n−r 0’s}))

■

11More generally, we could have chosen v_{i_{1}}, …, v_{i_{r}} for input. Since renaming of variables is up to us we can avoid the ugly notational acrobatics that this choice entails.

12Compare: A Turing machine is initialized with the input anywhere on its two-way infinite tape. It is assumed that the tape is automatically initialized everywhere else with the blank symbol. We then let the machine run.

13Since λv⃗.P (v⃗) has all its components in PR for all choices of P, all loop programs terminate.

We also define

Definition 2.2

ℒ = {P v⃗_{r} ; v_{k} : P ∈ L ∧ the v⃗_{r} and v_{k} occur in P }

■

By 1.3, we have at once

Theorem 2.3 ℒ ⊆ PR.

The converse is true

Theorem 2.4 PR ⊆ ℒ.

Proof By induction on PR and brute-force programming:

Basis: λx.x + 1 is P_{X}^{X} where P is X = X + 1 (we have reverted to the “relaxed” metanotation). Similarly, λx⃗_{n}.x_{i} is P X⃗_{n} ; X_{i} where P is

X_{1} = X_{1}; X_{2} = X_{2}; …; X_{n} = X_{n}

The case of λx.0 is as easy.

How does one compute λx.f(g(x)) if g is G_{X}^{X} and f is F_{X}^{X}? One uses

\binom{G′}{F}_{X}^{X}

where G′ is G modified to avoid side-effects: One must ensure that all the variables of G other than X are set to 0 upon exit from G, for F expects all these variables to be 0 in order to compute f correctly. G′ does that, if necessary, by placing at the end of G several statements of the type Y = 0.

The general case f ∘ (g_{1}, …, g_{n}) is programmed similarly.

Finally, we indicate in pseudo-code how to compute f(x, y⃗_{n}) where

f(0, y⃗_{n}) = h(y⃗_{n})
f(x + 1, y⃗_{n}) = g(x, y⃗_{n}, f(x, y⃗_{n}))

assuming we have loop programs for h and g. The pseudo-code is

z= h(y⃗_{n})
i = 0

Loop x

z = g(i, y⃗_{n}, z) i = i + 1 end

Once again one has to eliminate side-effects. For example, y⃗_{n} must not change. Program G (for g) expects all the variables other than i, y⃗_{n}, z to hold 0 at each invocation. This must be ensured by explicit programming. ■

All in all

PR = ℒ

3 Incompleteness of PR

We can now see that PR cannot possibly contain all the intuitively computable total functions. We see this as follows:

(A) Since the language L is context free, we can decide (algorithmically, intuitively speaking) for any string α whether it belongs to L (is a well-formed program) or not.

(B) We can algorithmically build the list, List_{1}, of all strings over Σ: List by length; in each length group lexicographically.^{14}

(C) Simultaneously to building List_{1} build List_{2} as follows: For every string α generated in List_{1}, copy it into List_{2} iff α ∈ L (which we can test by (A)).

(D) Simultaneously to building List_{2} build List_{3}: For every P (program) copied in List_{2} copy all the finitely many strings P_{Y}^{X} (for all choices of X and Y in P) alphabetically (think of the string as “P; X; Y ”).

At the end of all this we have an algorithmic list of \underline{all} the functions λx.f(x) of PR, listed by their aliases, the P_{Y}^{X}. Let us call this list

f_{0}, f_{1}, f_{2}, …, f_{x}, …

By Cantor’s “diagonalization method” we define a new function d for all x as follows:

d(x) = f_{x}(x) + 1  (1)

Two observations:

1. d is total (obvious, since each f_{x} is) and \underline{intuitively} computable. Indeed, to compute d(a) generate the lists long enough until you have the a-th item (counting as in 0, 1, 2, …, a) in List_{3}. This item has the format P_{Y}^{X}. I.e., we have a loop program and designated input (one) and output variables. Start this program with input the value a (in X). On termination add 1 to what Y holds and return. This is d(a).

2. d is not in the list! For otherwise, d = f_{i} for some i ≥ 0. We get a contradiction:

f_{i}(i) =^{by d=f_{i}} d(i) =^{by (1) above} f_{i}(i) + 1

References

[MR67] A. R. Meyer and D. M. Ritchie, Computational complexity and program structure, Technical Report RC-1817, IBM, 1967.

14Fix the ordering of Σ as listed in (1) on p.2.