1
LECTURE #5 (Sept. 23; Continued)
Before we get more immersed into partial functions let us redefine equality
for function calls.
0.0.1 Definition. Let λ⃗x.f(⃗xn) and λ⃗y.g(⃗ym).
We extend the notion of equality f(⃗an) = g(⃗bm) to include the case of undefined calls:
For any ⃗an and ⃗bm, f(⃗an) = g(⃗bm) means precisely one of • Forsomek∈N,f(⃗an)=kandg(⃗bm)=k
• f(⃗an) ↑ and g(⃗bm) ↑
For short,
f(⃗an) = g(⃗bm) ≡ (∃z)f(⃗an) = z ∧ g(⃗bm) = z ∨ f(⃗an) ↑ ∧g(⃗bm) ↑
The definition is due to Kleene and he preferred, as I do in the text, to use a new symbol for the extended equality, namely ≃.
Regardless, by way of this note we agree to use the same symbol for equal-
ity for both total and nontotal calls, namely, “=” (this convention is common
in the literature, e.g., [Rog67]).
EECS 2001Z. George Tourlakis. Winter 2019
2
0.0.2 Lemma. If f = prim(h,g) and h and g are total, then so is f.
Proof. Let f be given by:
f(0,⃗y) = h(⃗y)
f (x + 1, ⃗y) = g(x, ⃗y, f (x, ⃗y))
We do induction on x to prove
“For all x, ⃗y, f (x, ⃗y) ↓” (∗)
Basis. x = 0: Well, f(0,⃗y) = h(⃗y), but h(⃗y) ↓ for all ⃗y, so
f(0,⃗y) ↓ for all ⃗y (∗∗)
As I.H. (Induction Hypothesis) take that
f(x,⃗y) ↓ for all ⃗y and fixed x (†)
Do the Induction Step (I.S.) to show
f (x + 1, ⃗y) ↓ for all ⃗y and the fixed x of (†) (‡)
Well, by (†) and the assumption on g,
gx,⃗y,f(x,⃗y) ↓, for all ⃗y and the fixed x of (†)
which says the same thing as (‡).
EECS 2001Z. George Tourlakis. Winter 2019
3
0.0.3 Corollary. R is closed under primitive recursion. Proof. Let h and g be in R. Then they are in P. But then prim(h,g) ∈ P as
we showed in class/text and Notes #2.
By 0.0.2, prim(h, g) is total.
By definition of R, as the subset of P that contains all total functions
of P, we have prim(h,g) ∈ R.
Why all this dance in colour above? Because to prove f ∈ R you need TWO
things: That 1. f ∈ P
AND
2. f is total
But aren’t all the total functions in R anyway? NO! They need to be computable too!
We will see in this course soon that NOT all total func- tions are computable!
EECS 2001Z. George Tourlakis. Winter 2019
0.0.1 Primitive Recursive Functions
We saw that
1. The successor —S
2. zero —Z
3. and the generalised identity functions —Uin = λ⃗xn.xi are all in P
Thus, not only are they “intuitively computable”, but they are so in a precise mathematical sense:
each is computable by a URM.
We have also shown that “computability” of functions is preserved by the operations of composition, primitive recursion, and unbounded search.
In this subsection we will explore the properties of the important set of func- tions known as primitive recursive.
Most people introduce them via derivations just as one intro- duces the theorems of logic via proofs, as in the definition below.
EECS 2001Z. George Tourlakis. Winter 2019
4
A PR-derivation is a finite (ordered!) sequence of number- theoretic functions∗
f1,f2,f3,…,fi,…,fn (1)
such that, for each i, one of the following holds 1. fi ∈ I.
2. fi = prim(fj,fk) and j < i and k < i —that is, fj,fk appear to the left of fi.
3. fi = λ⃗y.gr1(⃗y), r2(⃗y), . . . , rm(⃗y), and all of the λ⃗y.rq(⃗y) and λ⃗xm.g(⃗xm) appear to the left of fi in the sequence.
Any fi in a derivation is called a derived function.† The set of primitive recursive functions, PR, is all
those that are derived. That is,
Def
PR = {f : f is derived}
The above definition defines essentially what Dedekind ([Ded88]) called “re- cursive” functions.
Subsequently they were renamed to primitive recursive allowing the unqualified term recursive to be synonymous with (total) computable and apply to the functions of R.
∗Recall: That is, left field is Nn for some n > 0, and right field is N.
†Strictly speaking, primitive recursively derived, but we will not considered other sets of derived functions, so we omit the qualification.
EECS 2001Z. George Tourlakis. Winter 2019
5
0.0.4 Definition. (PR-derivations; PR-functions) The set n
I= S,Z, Ui n≥i>0 is the set of Initial PR functions.
6
0.0.5 Lemma. The concatenation of two derivations is a deriva- tion.
Proof. Let
and
f1,f2,f3,…,fi,…,fn (1) g1,g2,g3,…,gj,…,gm (2)
be two derivations. Then so is
f1,f2,f3,…,fi,…,fn,g1,g2,g3,…,gj,…,gm
because of the fact that each of the fi and gj satisfies the three cases of Defini- tion 0.0.4 in the standalone derivations (1) and (2). But this property of the fi and gj is preserved after concatenation.
EECS 2001Z. George Tourlakis. Winter 2019
Lecture #6 (Sept. 28)
0.0.6 Corollary. The concatenation of any finite number of derivations is a derivation.
0.0.7 Lemma. If
f1,f2,f3,…,fk,fk+1,…,fn is a derivation, then so is f1,f2,f3,…,fk.
Proof. In f1,f2,f3,…,fk every fm, for 1 ≤ m ≤ k, satisfies 1.–3. of Defini- tion 0.0.4 since all conditions are in terms of what fm is, or what lies to the left of fm. Chopping the “tail” fk+1, . . . , fn in no way affects what lies to the left of fm, for 1 ≤ m ≤ k.
EECS 2001Z. George Tourlakis. Winter 2019
7
8
0.0.8 Corollary. f ∈ PR iff f appears at the end of some
derivation.
Proof.
(a) The If. Say g1,…,gn, is a derivation. Since f occurs in it, f ∈ PR by 0.0.4.
(b) The Only If. Say f ∈ PR. Then, by 0.0.4,
g1,…,gm, ,gm+2,…,gr (1)
for some derivation like the (1) above.
By 0.0.7, g1, . . . , gm, is also a derivation.
EECS 2001Z. George Tourlakis. Winter 2019
f
f
f
9
0.0.9 Theorem. PR is closed under composition and prim- itive recursion.
Proof.
• Closure under primitive recursion. So let λ⃗y.h(⃗y) and λx⃗yz.g(x,⃗y,z) be in PR. Thus we have derivations
h1,h2,h3,…,hn, (1) g1,g2,g3,…,gm, (2)
and
Then the following is a derivation by 0.0.5.
Therefore so is
h1,h2,h3,…,hn, ,g1,g2,g3,…,gm,
h1,h2,h3,…,hn, ,g1,g2,g3,…,gm, ,prim(h,g) by applying step 2 of Definition 0.0.4.
This implies prim(h, g) ∈ PR by 0.0.4.
• Closure under composition. So let λ⃗y.h(⃗xn) and λ⃗y.gi(⃗y), for 1 ≤ i ≤ n,
be in PR. By 0.0.4 we have derivations
h
g
h
g
h
g
…,
h
and
By 0.0.5,
(3)
, for 1 ≤ i ≤ n (4)
, ,…,
…,
gi
…,
h
…,
g1
…,
gn
is a derivation, and by 0.0.4, case 3, so is
, ,…, ,λ⃗y.h(g1(⃗y),…,gn(⃗y))
This implies λ⃗y.h(g1(⃗y), . . . , gn(⃗y)) ∈ PR by 0.0.4.
EECS 2001Z. George Tourlakis. Winter 2019
…,
h
…,
g1
…,
gn
0.0.10 Remark. How do you prove that some f ∈ PR? Answer. By building a derivation
g1,…,gm,
After a while this becomes easier because
you might know an h and g in PR such that f = prim(h,g), oryoumightknowsomeg,h1,…,hm inPR,suchthatf =λ⃗y.gh1(⃗y),…,hm(⃗y). If so, just apply 0.0.9.
How do you prove that ALL f ∈ PR have a property Q —that is, for all f, Q(f) is true?
Answer. By doing induction on the derivation length off.
f
10
EECS 2001Z. George Tourlakis. Winter 2019
11
Here are two examples demonstarting the above ques- tions and their answers.
0.0.11 Example. (1) To demonstrate the first Answer above (0.0.10), show (prove) that λxy.x + y ∈ PR. Well, observe that
0+y=y
(x + 1) + y = (x + y) + 1
Does the above look like a primitive recursion?
Well, almost.
However, the first equation should have a function call “H(y)” on the rhs but instead has just a variable y —the input!
Also the second equation should have a rhs like “G(x, y, x + y)”. We can do that!
Take H = U1 and G = SU3 —NOTE the “SU3” with no brackets around U3; this is normal practise!
Be sure to agree that we now have
•
0 + y = H(y)
(x+1)+y=G x,y,x+y
• The functions H = U1 (initial) and G = SU3 (composition)
are in PR. By 0.0.9 so is λxy.x + y.
In terms of derivations, we have produced the derivation:
U1, S, U3, SU3, prim U1, SU3
λxy.x+y
EECS 2001Z. George Tourlakis. Winter 2019
12 (2) To demonstrate the second Answer above (0.0.10), show (prove) that every
f ∈ PR is total. Induction on derivation length, n, where f occurs. Basis. n = 1. Then f is the only function in the derivation. Thus it must
be one of S, Z, or Uim. But all these are total.
I.H. (Induction Hypothesis) Fix an l. Assume that the claim is true for all f that occur at the end of derivations of lengths n ≤ l. That is, we assume that all such f are total.
I.S. (Induction Step) Prove that the claim is true for all f that occur at the end of a derivation —see 0.0.8— of length n = l + 1.
g1,…,gl, (1)
• f ∈ I. But we argued this under Basis.
• f = prim(h,g), where h and g are among the g1,…,gl. By the I.H. h and g are total. Elaboration: Any such gi is at the end of a derivation of length ≤ l. So I.H. kicks in.
But then so is f by Lemma 0.0.2.
• f = λ⃗y.hq1(⃗y),…,qt(⃗y), where the functions h and q1,…,qt are
among the g1,…,gl. By the I.H. h and q1,…,qt are total. But then so is f by a Lemma in the Notes #2, when we proved that R is closed
We have three subcases:
under composition.
EECS 2001Z. George Tourlakis. Winter 2019
f
13
0.0.12 Example. If λxyw.f(x, y, w) and λz.g(z) are in PR, how about λxzw.f(x,g(z),w)?
It is in PR since, by COMPOSITION,
f (x, g(z), w) = f (U13(x, z, w), g(U23(x, z, w)), U3(x, z, w))
and the Uin are all primitive recursive.
The reader will see at once that to the right of “=” we have correctly formed compositions as expected by the “rigid” defini- tion of composition given in class.
Similarly, for the same functions above,
(1) λyw.f(2, y, w) is in PR. Indeed, this function can be obtained by composi- tion, since
f(2, y, w) = fSSZU12(y, w), y, w
where I wrote “SSZ(. . .)” as short for S(S(Z(. . .))) for visual clarity.
Clearly, using SSZU2(y,w) above works as well.
(2) λxyw.f(y, x, w) is in PR. Indeed, this function can be obtained by compo-
sition, since
f(y, x, w) = fU23(x, y, w), U13(x, y, w), U3(x, y, w)
In this connection, note that while λxy.g(x, y) = λyx.g(y, x), yet λxy.g(x, y) ̸= λxy.g(y, x) in general.
For example, λxy.x −. y asks that.we subtract the second input
(y) from the first (x), but λxy.y − x asks that we subtract the first input (x) from the second (y).
(3) λxy.f(x,y,x) is in PR. Indeed, this function can be obtained by composi- tion, since
f(x, y, x) = fU12(x, y), U2(x, y), U12(x, y) EECS 2001Z. George Tourlakis. Winter 2019
14
(4) λxyzwu.f(x, y, w) is in PR. Indeed, this function can be obtained by com- position, since
λxyzwu.f (x, y, w) =
λxyzwu.f(U15(x, y, z, w, u), U25(x, y, z, w, u), U45(x, y, z, w, u))
The above four examples are summarised, named, and generalised in the following straightforward exercise:
0.0.13 Exercise. (The [Grz53] Substitution Operations) PR is closed un- der the following operations:
(i) Substitution of a function invocation for a variable:
From λ⃗xy⃗z.f(⃗x,y,⃗z) and λw⃗.g(w⃗) obtain λ⃗xw⃗⃗z.f(⃗x,g(w⃗),⃗z).
(ii) Substitution of a constant for a variable: From λ⃗xy⃗z.f(⃗x,y,⃗z) obtain λ⃗x⃗z.f(⃗x,k,⃗z).
(iii) Interchange of two variables:
From λ⃗xy⃗zw⃗u.f(⃗x,y,⃗z,w,⃗u) obtain λ⃗xy⃗zw⃗u.f(⃗x,w,⃗z,y,⃗u).
(iv) Identification of two variables:
From λ⃗xy⃗zw⃗u.f(⃗x,y,⃗z,w,⃗u) obtain λ⃗xy⃗z⃗u.f(⃗x,y,⃗z,y,⃗u).
(v) Introduction of “don’t care” variables: From λ⃗x.f(⃗x) obtain λ⃗x⃗z.f(⃗x).
By 0.0.13 composition can simulate the Grzegorczyk operations if the initial functions I are present.
Of course, (i) alone can in turn simulate composition.
With these comments out of the way, we see that the “rigidity” of the definition of composition is gone.
EECS 2001Z. George Tourlakis. Winter 2019
15 0.0.14 Example. The definition of primitive recursion is also rigid. How-
ever this is also an illusion.
Take p(0) = 0 and p(x + 1) = x —this one defining
p = λx.x −. 1 —does not fit the schema.
The schema requires the defined function to have one more variable than the basis, so no one-variable function can be directly defined!
We can get around this.
Define first p = λxy.x −. 1 as follows: p(0, y) = 0 and p ( x + 1 , y ) = x .
Now this can be dressed up according to the syntax of the schema, p(0,y) = Z(y)
p(x + 1, y)= U13(x, y, p(x, y)) that is, p = prim(Z, U13).
Then we can get p by (Grzegorczyk) substitution: p = λx.p(x, 0).
Incidentally, this shows that both p and p are in PR:
• p = prim(Z, U13) is in PR since Z and U13 are, then
invoking 0.0.9.
• p=λx.p(x,0)isinPRsincepis,theninvoking0.0.13.
EECS 2001Z. George Tourlakis. Winter 2019
Another rigidity in the definition of primitive recur- sion is that, apparently, one can use only the first vari- able as the iterating variable.
Not so. This is also an illusion.
Consider, for example, sub = λxy.x −. y, hence x−. 0=xandx−. (y+1)=p(x−. y)
Clearly, sub(x, 0) = x and sub(x, y + 1) = p(sub(x, y)) is correct semantically, but the format is wrong:
16
Lecture # 7 (Sept. 30)
We are not supposed to iterate along the second variable!
Well, define instead sub = λxy.y −. x:
So
That is,
y−.0 =y
y −. (x+1)= py −. x
1 sub(0, y) = U1 (y)
3 sub(x+1,y)=p U3(x,y,sub(x,y))
Then, using variable swapping [Grzegorczyk operation (iii)], we can get sub:
sub = λxy.sub(y, x).
Clearly, both sub and sub are in PR. EECS 2001Z. George Tourlakis. Winter 2019
17 0.0.15 Exercise. Prove that λxy.x × y is primitive recursive. Of course, we
will usually write multiplication x × y in “implied notation”, xy.
EECS 2001Z. George Tourlakis. Winter 2019
18
0.0.16 Example. The very important “ switch” (or “if-then- else”) function
sw = λxyz.if x = 0 then y else z is primitive recursive.
It is directly obtained by primitive recursion on initial
functions: sw(0,y,z)=yandsw(x+1,y,z)=z.
EECS 2001Z. George Tourlakis. Winter 2019
0.0.17 Exercise. PR ⊆ R.
Indeed, the above inclusion is proper, as we will see later.
19
EECS 2001Z. George Tourlakis. Winter 2019
20
0.0.18 Example. Consider the exponential function xy given by x0 =1
xy+1= xyx
Thus,
ifx=0,thenxy =1,butxy =0forally>0.
BUT that xy is “mathematically” undefined when x = y = 0.‡
Thus, by Example 0.0.11 the exponential cannot be a primi- tive recursive function!
This is rather silly, since the computational process for the exponential is so straightforward; thus it is ridiculous to de-
clare the function non-PR.
After all, we know exactly where and how it is un-
defined and we can remove this undefinability by redefining “xy ”
so that “00 = 1”.
In computability we do this kind of redefini-
tion a lot in order to remove easily recognisable points of “non definition” of calculable functions.
We will see further examples, such as the remainder, quotient, and logarithm functions.
BUT also examples where we CANNOT do this; and WHY.
‡In first-year university calculus we learn that “00” is an “indeterminate form”. EECS 2001Z. George Tourlakis. Winter 2019
21 0.0.19 Definition. A relation R(⃗x) is (primitive) recursive iff its characteristic
function,
0 ifR(⃗x) cR = λ⃗x. 1 if ¬R(⃗x)
is (primitive) recursive. The set of all primitive recursive (re- spectively, recursive) relations is denoted by PR∗ (re- spectively, R∗).
Computability theory practitioners often call relations predicates.
EECS 2001Z. George Tourlakis. Winter 2019
22
It is clear that one can go from relation to characteristic function and back in a unique way,
Thus, we may think of relations as “0-1 valued” func- tions.
The concept of relation simplifies the further development of the theory
of primitive recursive functions.
The following is useful:
0.0.20 Proposition. R(⃗x) ∈ PR∗ iff some f ∈ PR exists such that, for all ⃗x, R(⃗x) ≡ f(⃗x) = 0.
Proof. For the if-part, I want cR ∈ PR.
This is so since cR = λ⃗x.1 −. (1 −. f (⃗x)) (using Grzegorczyk
substitution and λxy.x −. y ∈ PR; cf. 0.0.14).
For the only if-part, f = cR will do.
0.0.21 Corollary. R(⃗x) ∈ R∗ iff some f ∈ R exists such that, for all ⃗x, R(⃗x) ≡ f ( ⃗x ) = 0 .
Proof. By the above proof, and 0.0.17.
0.0.22 Corollary. PR∗ ⊆ R∗.
Proof. By the above corollary and 0.0.17.
EECS 2001Z. George Tourlakis. Winter 2019
23
0.0.23 Theorem. PR∗ is closed under the Boolean opera- tions.
Proof. It suffices to look at the cases of ¬ and ∨, since R → Q ≡ ¬R ∨ Q, R ∧ Q ≡ ¬(¬R ∨ ¬Q) and R ≡ Q is short for (R → Q) ∧ (Q → P ).
(¬) Say, R(⃗x) ∈ PR∗. Thus (0.0.19), cR ∈ PR. But then c¬R ∈ PR, since c¬R = λ⃗x.1 −. cR(⃗x), by Grzegorczyk substitution and λxy.x −. y ∈ PR.
(∨) Let R(⃗x) ∈ PR∗ and Q(⃗y) ∈ PR∗. Then λ⃗x⃗y.cR∨Q(⃗x,⃗y) is given by cR∨Q(⃗x, ⃗y) = if R(⃗x) then 0 else cQ(⃗y)
and therefore is in PR.
“if R(⃗x)” above means “if cR(⃗x) = 0” 0.0.24 Remark. Alternatively, for the ∨ case above, note
that cR∨Q(⃗x, ⃗y) = cR(⃗x) × cQ(⃗y) and invoke 0.0.15. 0.0.25 Corollary. R∗ is closed under the Boolean operations.
Proof. As above, mindful of 0.0.17.
0.0.26Example. Therelationsx≤y,x