1
A Programming Formalism for PR* A brief note that assumes access to [Tou12].
George Tourlakis October 21, 2020
Lecture #9 (continued) Oct. 7.
Syntax and Semantics of Loop Programs
Loop programs were introduced by D. Ritchie and A. Meyer ([MR67]) as program-theoretic counterpart to the number theo- retic 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.
*Supplementary lecture notes for EECS2001B; Fall 2020
1
Loop programs are very similar to programs written in FOR- TRAN,
but have a number of simplifications,
notably they lack an unrestricted do-while instruction (equiva-
lently, there is NO goto instruction).
2
What they do have is
(1) Each program references (uses) a finite number of N-valued 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 a sequence of syntactically valid instructions (which in 1.1 will be called a “loop pro- gram”). The Loop part is matched or balanced by the end part as it will become evident by the inductive defi- nition below (1.1).
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 ′′ for variables—i.e., we will continue using metanotation. 34
3
Informally, the structure of loop programs can be defined by induction:
Definition 1.1
• Every ONE instruction of type (i)–(iii) standing by itself is a loop program.
If we already have two loop programs P and Q, then so are • P;Q, built by superposition (concatenation)
normally written vertically, without the separator “;”, like this:
and,
4
P Q
• for any variable X (that may or may not be in P ),
Loop X; P; end, is a program, called the loop closure (of P ),
and normally written vertically without separators “;” like this:
Loop X P
end
5
Lecture #10, Oct. 19
Definition 1.2 The set of all loop programs will be denoted by L. The informal semantics of loop programs are precisely those
given in [Tou12].
They are almost identical to the semantics of the URM pro- grams.
6
1. A loop program terminates “if it has nothing to do”, that is, If the current instruction is EMPTY.
2. All three assignment statements behave as in any program- ming language,
and after execution of any such instruction, the instruction below it (if any) is the next CURRENT instruction.
3. When the instruction “Loop X; P; end”
becomes current, its execution DOES (a) or (b) below:
We view the Loop-end construct as an “instruction” just
as a begin-end block is in, say, Pascal.
(a) NOTHING, if X = 0 at that time
and program execution moves to the first instruction be- low the loop.
(b) If X = a > 0 initially, then the instruction execution has the same effect as the program
P P
a copies . P
7
So, the semantics of Loop-end are such that the number of times around the loop is NOT affected if the program CHANGES X by an assignment statement inside the loop!
8
The symbol PX⃗n has exactly the same meaning as for the Y
URMs, but here “P ” is some loop program
It is the function computed by loop program P if we use X⃗n =X1,X2,…,Xn astheinputandY astheoutputvariables.
AllPX⃗n aretotal. Y
This is trivial to prove by induction on the formation of P — that ALL loop Programs Terminate.
Basis: Let P be a one-instruction program. By 1 and 3 of page 7, such a program terminates.
I.H. Fix and Assume for programs P and Q.
I.S.
• What about the program
P Q
By the I.H. starting at the top of program P we eventually overshoot it and make the first instruction of Q current.
By I.H. again, we eventually overshoot Q and the whole computation ends.
9
• What about the program LoopX;P;end
Well, if X = 0 initially, then this terminates (does nothing). So suppose X has the value a > 0 initially.
Then the program behaves like
P P
a copies . P
By the I.H. for each copy of P above when started with its first instruction, the instruction pointer of the computation will eventually overshoot the copy’s last instruction.
But then starting the computation with the 1st instruction of the 1st P, eventually the computation executes the 1st in- struction of the 2nd P ,
then, eventually, that of the 3rd P . . .
and, then, eventually, that of the last (a-th) P .
We noted that each copy of P will be overshot by the compu- tation; THUS the overall computation will be over after the LAST copy has been overshot. PROVED!
10
Definition 1.3 We define the set of loop programmable functions, L:
The symbol L stands for {PX⃗n : P ∈ L}. Y
11
Two examples. Refer the computation of λx.rem(x, 2) and λx.⌊x/2⌋ earlier.
If we let f = λx.rem(x, 2) we saw that the following sim. recursion computes f.
f(0) = 0 g(0) = 1 f(x+1) =g(x) g(x + 1) = f(x)
(1)
As a loop program this is implemented as the program P be- low —that is, f = PFX .
G←G+1 Loop X T←F F←G G←T end
12
As for λx.⌊x/2⌋ we saw earlier that if f = λx.⌊x/2⌋ then we have:
Loop X T←F F←G T←T+1 G←T end
f(0) = 0
g(0) = 0 f(x+1) =g(x) g(x+1) =f(x)+1
(2)
If P is the name of the above program, then PFX = f .
13
Subtracting by adding!
The program QX below computes λx.x −. 1.
How?
X lagsfromT byone. AttheendoftheloopT holdsthe original value of X, but X is ONE behind its original value!
T←0 Loop X X←T T←T+1 end
14
Addition
Program P below computes λxy.x + y as PXY . Y
Loop X Y←Y+1 end
15
Multiplication
Program Q below computes λxy.x × y as QXY . Z
Loop X Loop Y
Z←Z+1
end end
Why? Because we add 1 —X × Y times— to Z that starts as 0.
16
2 PR⊆L
Theorem 2.1 PR ⊆ L.
Proof By induction over PR and brute-force programming we are proving THIS property of ALL f ∈ PR:
“f is loop programmable”.
Basis:λx.x+1isPX wherePisX←X+1.
Similarly,λ⃗xn.xiisPX⃗n wherePis Xi
X1 ← X1;X2 ← X2;…;Xn ← Xn
The case of λx.0 is as easy.
17
Propagation of the property we are proving with Grzegorczyk substitution.
Just probe the function substitution case.
How does one compute λ⃗x⃗y.f(g(⃗x),⃗y) if g = GX⃗ and f = Z
F Z Y⃗ ? W
Same as with URM programs.
One uses program concatenation and minds that Z is the only variable common between F and G.
G X⃗ Y⃗
F
18
W
Propagation with primitive recursion.
So,sayh=HY⃗ andg=GX,Y⃗,Z whereHandGareinL. ZZ
We indicate in pseudo-code how to compute f = prim(h, g). We have
f(0,⃗yn) = h(⃗yn)
f (x + 1, ⃗yn) = g(x, ⃗yn, f (x, ⃗yn))
The pseudo-code is
z← h(⃗yn) i←0
Loop x
z ← g(i, ⃗yn, z)
i←i+1 end
Computed as HY⃗n Z
Computed as GI,Y⃗n,Z Z
See the similar more complicated programming for URMs to
recall precautions needed to avoid side-effects.
19
3 L⊆PR
To handle the converse of 2.1 we will simulate the computation of loop program P by an array of primitive recursive functions.
Definition 3.1 For any P ∈ L and any variable Y in P , the sym- bolPY isanabbreviationofPX⃗n,whereX⃗nareallthevariables
that occur in P .
Y
Lemma3.2 For any P ∈ L and any variable Y in P, we have thatPY ∈PR.
Proof
(A) For the Basis, we have cases: •PisX←0.ThenPX =λx.0∈PR.
•PisX←Y.ThenPX =λxy.y∈PR,whilePY = λxy.y ∈ PR.
•PisX←X+1.ThenPX =λx.x+1∈PR
20
Let us next do the induction step: (B) P is Q; R.
(i) Case where NO variables are common between Q and R.
Let the Q variables be ⃗zk and the R variables be ⃗um. •WhatcanwesayaboutQ;R ?
Let λ⃗zk.f(⃗zk) = Qzi.
f ∈PRbytheI.H.
But then, so is λ⃗zk⃗um.f(⃗zk) by Grzegorczyk Ops.
ButthisisQ;R . zi
• Similarly we argue for Q; R
uj
.
21
zi
Lecture #11. Oct. 21
(ii) Case where ⃗yn are common between Q and R.
⃗z and ⃗u —just as in case (i) above— are the NON-common
variables.
Thus the set of variables of Q; R is ⃗yn⃗zk⃗um
Now, pick an output variable wi.
• If wi is among the zj, then we are back to the first
bullet of case (i).
Nothing that R does can change zj .
• So let the wi be a component of the vector ⃗yn⃗um instead. This case is fully captured by the figure below.
22
inputs
outputs
inputs
R outputs
Q
23
(C) P is Loop x; Q; end.
There are two subcases: x in Q; or NOT.
(a) x not in Q:
So, let ⃗yn be all the variables of Q; x is NOT one of them. Let
and, for i = 1,…,n,
denote Px (5) denote Pyi (6)
λx⃗yn.f0(x, ⃗yn)
λx⃗yn.fi(x, ⃗yn)
where x —being an input variable— holds the initial value we give to it before the program P starts.
In what follows we will refer to this initial value
of x as “k”.
Moreover, let
denote Qyi (7)
By the I.H., the gi are in PR for i = 1,2,…,n.
We want to prove that the functions in (5) and (6) are also in PR.
Since f0 = λx⃗yn.x (Why?), weonlydealwiththefi fori>0.
λ⃗yn.gi(⃗yn)
24
The plan is to set up a simultaneous recursion that produces the fi from the gi.
Now imagine the computation of P with input x, y1, . . . , yn. We have two sub-subcases:
• x = 0.
In this sub-subcase, the loop is skipped and no vari- ables are changed by the program. In terms of (5) and (6), what I just said translates into
and
f0(0,⃗yn) = 0 (8) fi(0,⃗yn) = yi, for i = 1,…,n (9)
• x = k + 1, i.e., positive. The effect of P is
Q Q
k copies
.
Q Q
What is fi(k + 1,⃗yn), for i > 0?
Well, consult the picture below:
(10)
25
inputs
outputs
inputs
outputs
We now have a simultaneous primitive recursion that yields the fi from the gi. The gi being in PR by the I.H. on Q, so are the fi.
26
(b) x in Q:
So, let x, ⃗yn be all the variables of Q. Let
λx⃗yn.f0(x, ⃗yn) denote Px (11) and, for i = 1,…,n,
Moreover, let
λx⃗yn.fi(x, ⃗yn) denote Pyi (12) λx⃗yn.g0(x, ⃗yn) denote Qx (13)
λx⃗yn.gi(x, ⃗yn) denote Qyi (14) By the I.H., the gi are in PR for i = 1,2,…,n.
We want to prove that the functions in (11) and (12) are also in PR by employing an appropriate simultaneous recursion. The basis equations are the same as (8) and (9).
27
For x = k + 1 we simply consult the figure below, to yield the recurrence equations
inputs
outputs
inputs
outputs
fj(k+1,⃗yn) = gj(f0(k,⃗yn),f1(k,⃗yn),…,fn(k,⃗yn)),j = 0,…,n Asthegj areinPR,soarethefj.
At the end of all this we have the proof of the Lemma.
28
We can now prove
Theorem 3.3 L ⊆ PR.
Proof WemustshowthatifP ∈LthenforanychoiceofX⃗n,Y
in P we have
P X⃗ n ∈ P R Y
So pick a P and also X⃗n,Y in it.
Let Z⃗m the rest of the variables (the non-input variables) of P ,
and let
and
f = P Y = P X⃗ n , Z⃗ m Y
g = P X⃗ n Y
m zeros
⃗⃗
g(Xn) = f(Xn,0,…,0)
By Grzegorczyk substitution, g = PX⃗n ∈ PR. Y
By the lemma, f ∈ PR. But
All in all, we have that
PR = L 29
4 Incompleteness of PR
We can now see that PR cannot possibly contain all the intu- itively computable total functions. We see this as follows:
(A) It is immediately believable that we can write a program that checks if a string over the alphabet
Σ = {X,0,1,+,←,; ,Loop,end}
of loop programs is a correctly formed program or not.
BTW, the symbols X and 1 above generate all the variables, X1, X11, X111, X1111, . . .
We will not ever write variables down as what they really are —“X 1 . . . 1”— but we will continue using metasymbols
k 1s like
X,Y,Z,A,B,X′′,Y′′′,x,y,z′′′ 23 15
etc., for variables!
30
(B) We can algorithmically build the list, List1, of ALL strings over Σ:
List by length; and in each length group lexicographically.2 (C) Simultaneously to building List1 build List2 as follows:
For every string α generated in List1, copy it into List2 iff α ∈ L (which we can test by (A)).
(D) Simultaneously to building List2 build List3:
For every P (program) copied in List2 copy all the finitely many strings PYX (for all choices of X and Y in P ) alphabetically (thinkofthestringPYX as“P;X;Y”).
At the end of all this we have an algorithmic list of all the functions λx.f(x) of PR,
listed by their aliases, the PYX programs.
Let us call this list of ALL the one-argument P R FUNCTIONS
f0,f1,f2,…,fx,… (1)
Each fi is a λx.fi(x) 2Fix the ordering of Σ as listed above.
31
4.1 A Universal function for unary PR functions
At the end of all this we got a universal or enumerating func- tion U(PR) for all the unary functions functions in PR.
That is the function of TWO arguments
U(PR) = λix.fi(x) (2)
U(PR)(i,x) = fi(x).
What do I mean by “Universal”?
Definition 4.1 U (P R) of (2) is universal or enumerating for all
the unary functions of PR meaning it has two properties:
1. If g ∈ PR is unary, then there is an i such that g = λx.U(PR)(i,x)
and
2. Conversely, for every i ∈ N, λx.U(PR)(i,x) ∈ PR.
32
Theorem 4.2 The function of two variables, λix.U(PR)(i,x) is computable informally.
Proof HereishowtocalculateU(PR)(i,x)foreachgivenianda:
1. Find the i-th PYX in the enumeration (1) that we have built
in (D) above. That is, the fi in List3.
This does NOT mean we HAVE an infinite List sitting there:
It means: build List1 and simultaneously the lists List2 and List3 and stop once you got the i-th element of the latter List enumerated.
2. Now, run the PYX you just found with input a into X. This terminates!
After termination Y holds fi(a) = U(PR)(i,a).
Important. We repeat for posterity TWO by-products of 4.1 and 4.2:
• The informally computable Enumeration function U(PR) is total.
• λx.U(PR)(i,x) = fi for all i.
33
Theorem 4.3 U (P R) is NOT primitive recursive.
Proof If it is, then so is λx.U(PR)(x,x) + 1 by Grzegorczyk operations. As this is a unary PR function, we must have an i such that
U(PR)(x,x) + 1 = U(PR)(i,x), for all x (3)
Setting i into x in (3) we get the contradiction
U(PR)(i,i)+1 = U(PR)(i,i)
Remark. 4.4 Thus λix.U(PR)(i,x) acts as the COMPILER of a stored program computer:
You give it a (pointer to a) PROGRAM i and DATA x and it simulates the Program (at address) i on the Data x!
We have just learnt in the above theorem that this compiler
CANNOT be programmed in the Loop-Programs Program-
ming Language!
34
References
[MR67] A. R. Meyer and D. M. Ritchie, Computational com- plexity and program structure, Technical Report RC- 1817, IBM, 1967.
[Tou12] G. Tourlakis, Theory of Computation, John Wiley & Sons, Hoboken, NJ, 2012.
35