Last time I gave an exercise, and a big part of the solution. See below (*).

Let me recall what happened, and illustrate perhaps a little more.

Apology for the type errors, please asks any question at any steps of your 
reading from combinators 1 to here and of course further. 

No doubt that post, like the last one, will seem complicated if you have not 
studied and train yourself a bit. But don’t hesitate to ask question. All this 
remains simple (compared to classical or quantum physics for example).

I have shown something rather extraordinary. I have defined very simple 
objects, the combinators, and provided two very simple axioms. 

K is a combinator
S is a combinator

If x and y is a combinator, then (x y), written xy if there is no risk of 
confusion, is a combinator. We say that it is the combinator resulting of the 
combinator x applied to the combinator y.
So the combinator xy applied to z can be written xyz, but the combinator x 
applied to yz must be written with  parentheses x(yz), or a confusion occurs.

The laws, rules, axioms are that, for all combinators x, y z

1) Kxy = x

2) Sxyz = xz(yz)

The extraordinary things which has been shown is that the combinators compute a 
large class of computable functions (from N to N): the so called class (set, 
collection) of “primitive recursive functions”. They were introduced by Gödel 
in his 1931 paper, and he called them “recursive”. For him it was just the 
functions that he needed to get its arithmetization of meta-arithmetic. But to 
get his beweisbar, provability predicate, Gödel was forced to add something, 
and we will have to add it too, to get the full Turing partial computable 
functions. That thing is the Mu operator. Note that Gödel, despite defining 
somehow the class of partial recursive function, and indeed “[]” is a universal 
Turing machine, he will miss this. There is no Gödel’s thesis. But eventually 
he will accept Church’s thesis, and call a “miracle” the closure of that set of 
functions for the diagonalisation procedure. 

Let me recall what the (more limited) class of “primitive recursive functions” 
consists in. It contains all “initial functions”, which are 

1) the zero function Z. Z(n) = 0 for each n. It is simply the constant 0. Here, 
we can use K0  where 0 denotes the Barendrecht numeral, that is the combinators 
that we have chosen to represents 0; which was I, so that Z = K0 = KI = K(SKK).

KIn = I (= 0, or if you prefer K(SKK)n = SKK).

I use “Z”, but it should not be confused with the zero tester, also named Z, 
and which is the combinator predicate Tt (equal to K when applied to 0, and to 
KI, when applied to a non null number, see preceding threads).

2) the successor function: s(n) = n+1.

With the Barendrecht numerals, 0, 1, 2, 3, … are I, VfI, Vf(VfI), Vf(Vf(VfI), 
so s is computed simply by Vf. V is the Vireo, and f is the false, which is 
here KI. Coincidently, the false and the zero function is played by the same 

And all projection functions I_m_n:

I_m_n(x1, x2, x3, … xn) = xm.

For example:

I_2_3 applied on (4, 5, 6) = 5 

With the combinators, it is obvious we have them all, for example, 

I_2_3 is simply [x][y][z]y.

You can use the ABF, or the ABCF, or the ABCDEF algorithm to make the 
extraction of the combinator if you want. I might as well do it, for those who 
still harbour some doubt :)

You recall that  [x][y][z]y is really put for [x] ([y]   ([z] y) ), so 

 [x] ([y]   ([z] y) )
= [x] ([y] Ky) by rule A:  [x]N (x does not occur in the combination N) = KN
= [x] K by rule C [x]Nx = N, again with x not occurring in N (here x is y, of 
= KK, again by rule A

Verification: KKxyz = Kyz = y. 

So I_2_3 = KK.

The existence of the ABF algorithm (and the proof of its correctness) ensures 
that we get all projections from NxNx .. xN in N.

That gives all initial functions, and to get all primitive recursive functions, 
we close that set for the rule of composition of functions, and for “primitive 
recursion”. By definition.

Composition means that we can compose the functions, and is made obvious by the 
presence of the blue bird B. Bxyz = x(yz). That it composes functions is seen 
more clearly if you write f for x and g for y, and x for z: Bfgx = f(gx). That 
if f applied to the result of applying g to x. More complex composition 
involving functions of many arguments can be done easily by repeating 
applications of B, or combinations of B.

The “Primitive recursion” is when we define a function on 0, and extends its 
definition by giving a rule to compute it from there. The most typical example 
is the factorial function:

F(0) = 1
F(x) = x * F(x-1)

If you have reminded that xyz implements “if x then y else z”, by using 
combinator predicate, which gives K (true, t) or KI (false, f), the factorial 
above, F is simply the combinator, with Z being the zero tester (not the 
constant 0 above!) satisfying the recursion relation:

Fx = Zx(VfI)(mx(F(Px))

Like we have already done for addition and multiplication, and parity, …

To solve that equation, we can replace x by y, so that x will become the fixed 

F’xy = Zy(VfI)(my(x(Px))

So F’ = [x][y]Zy(VfI)(my(x(Px))

And the factorial combinator is F = YF’, where Y is the paradoxical 
You can also use Smullyan’s method from scratch. Both are based on the idea 
that if Dx = T(xx), then DD = T(DD), which I have explained many times, in 
different threads.

The general case, or a more general case is, when G and H are two primitive 
recursive functions already defined

F(0,y) = H(y)
F(x, y) = G(x, y, F(x-1, y)).

Again, the combinators computing F is given by

Fxy = Zx(Hy)(Gxy(F(Px)y)


Fyz = Zy(Hz)(Gyz(F(Py)z)


F’xyz = Zy(Hz)(Gyz(F(Py)z)


F’ = [x][y][z]Zy(Hz)(Gyz(F(Py)z)

And so YF’ gives the combinator computing that F.


Now, we see that the SK-combinators compute a very large class of functions.

Can you see what is missing to get the full Turing universality?

In fact, the primitive recursive functions can be shown to be all, each of 
them, total functions, and they constituted obviously a recursive enumerable 
class of functions, so we could build a total computable function, non 
primitive recursive, by diagonalisation. (And repeat this in the constructive 
transfinite, for those wo remember the threads from some times ago).

Of course, as the primitive recursive functions are all total, we miss partial 
computable functions. The primitive recursive functions are not able to crash 
the computer, and so cannot imitate even the simple mocking bird M (Mx = xx, MM 
never stops).

We have primitive recursion, composition and a rich set of (total) initial 

What is crucially missing?

There is one operation, or control structure that is missing: the while 
instruction, allowing the machine to make test and move forward as long as some 
condition is not verified. A more “primitive” form is incarnated in the Mu 
operator: the operation of finding a natural number (the least one) verifying a 
primitive recursive condition.

That is how Kleene defined the class of the partial recursive function: it is 
the closure of the class of primitive recursive function for the Mu operator. 
That gives a class of functions identical with the class of programmable 
functions, or LISP-computable, or FORTRAN computable, or Turing computable 
(computable by a Turing machine), or Robinson-arithmetic computable, etc. This 
does not need Church thesis, as it can be proved. Church thesis just asserts 
that those class defines indeed the intuitively partial computable function.

So all we need to do now is to find a combinator computing the Mu operator.

============ The Mu operator ==============

What we cannot do is to ask the machine to search for a number having some 
property. If the machine is able to make such a search, we can crash it easily, 
by asking her to search for a number which does not exist. The poor machine 
will search a *long* time, and we usually say that we have crashed the 
computer. Such machine will never stop. That is something we cannot do with the 
primitive recursive function.

But it is easy to do this with the full recursion power of the combinator.

I show this first on a (primitive recursive) predicate of one argument A(x).

So the goal consists in finding the least number x such that A(x) is true.

Exemple: Mu PRIME = the least prime number, Mu even = the least even number, Mu 
different-of-oneself = a non stopping program searching number x different of 

Mu A = the least x such that A(x).

We cannot use primitive recursion, which reduce a problem for n to n-1, and 
stop the recursion call when getting at 0. Indeed that is why primitive 
recursion gives only total functions, defined everywhere. Here, we must start 
from 0, and make the recursive call on higher and higher value of x (x is a 
“Barendregt” natural number).

The idea is to initialise Mu on 0, and build the recursive call on an auxiliary 
function: Mu-AUX.

So we define Mu A by Mu-AUX A 0, 

And (Mu-AUX A x) =  (If (A x) then x else (A (sx)), with s representing the 
successor function (which was Vf) =   (Ax)x(Mu-AUX(sx))

That is: (Mu-AUX A x) = (Ax)x(Mu-AUX A (sx))

And then we eliminate the recursion by the usual method:

1) change of variable: 

(Mu-AUX y z) = (yz)z(Mu-AUX y (sz))

2) (Mu-AUX-1 x y z) = (yz)z(x y (sz))

So Mu-AUX-1 = [x][y][z](yz)z(x y (sz))

And Mu-AUX = Y Mu-AUX-1.

Now Mu x = Mu-AUX x 0

i.e Mu = [x](Mu-AUX x 0).


Adding variable does not change the difficulty (just the readability, a little 

Now we want to find the least number y such that R(x, y), for all x:

Mu R x = Mu-AUX R x 0


(Mu-AUX R x y) = (Rxy)y(Mu-AUX R x (sy))

And we eliminate the recursion by the usual method:

1) change of variable

(Mu-AUX y z w) = (yzw)w(Mu-AUX y z (sw))

2) Mu-AUX-1 x y z w) = (y z w)w(x y z (sw))

So Mu-AUX-1 = [x][y][z][w](y z w)w(x y z (sw))

And Mu-AUX = Y Mu-AUX-1.

So Mu R y = Mu-AUX R y 0.    (R represents the predicate here).

We can write Mu x y = Mu-AUX x y 0.

And Mu = [x][y](Mu-AUX x y 0).


At the course, a student asked me to do that last elimination of variable 

OK, but please reread the thread combinator 2 which explains in details the 

Mu = [x][y](MU-AUX x y 0) = [x][y]AxyB (A and B are just simple to read than 
Mu-AUX and 0). I will use the ABCF algorithm (see “combinators 2))
= [x] ([y]AxyB)
= [x] (S [y]Axy [y]B)
= [x] (S (Ax) (KB))
= S [x]S(Ax) [x](KB))
= S (S([x]S)([x]Ax))(K(KB))
= S(S(KS)A)(K(KB))

S(S(KS)A)(K(KB))xy =
S(KS)Ax(K(KB)x)y =
KSx(Ax)(KB)y =
S(Ax)(KB)y =
Axy(KBy) =

So Mu = S(S(KS)Mu-AUX)(K(K0))

Of course you can transform Mu-AUX too in the same way. Mu is a combinator!

So now, we have finished the proof that the combinators are Turing universal. 
They compute all partial recursive functions, and thus emulates all 

Next thread, the first and second recursion theorem. This will give the precise 
definitions of first person and third person points of view.
The first recursion theorem will be very easy, and is already done, in fact, 
thanks to Y. The second recursion theorem will need Gödel numbers, and asks for 
more work.
I might make an interlude on the relation between the combinators and the phi_i 
before, also.


(*) ============= For the preceding thread ====

Exercise (preparation for the proof of the Turing Universality).

Convince yourself that we can write programs for all so called “primitive 
recursive function”.

The class of primitive recursive functions (from N to N) is the class of 
functions, x_i are variables for numbers, 

1) containing the following “initial” functions,

a) For each n, m, with m < n, I_m_n(x1, x2, …. , xn) = xm  (the projection 
b) the constant 0: z(n) =  0 
c) the successor function s(n) = n + 1.

2) and close for the following operations:

a) composition of function (if f and g is in the class then [x] f(gx) is in the 
b) primitive recursion, if g and h is the class, then f defined by

fx0 = g(x)
fxy = h(x, f(x, py)) 

Quick solution: (ask if there is a problem):

1a) The projection functions:

We have already I_2_1, it is K, and I_2_2 it is KI. Obviously 

I_2_3 will be [y]xyz

And I_4_7 will be [t]xyztruv.


1b) The constant 0 is just K0.  Which is KI.

1c) the successor function is Vf

2a) The closure for composition is assured by the presence of the combinator B, 
which composes function:
Bxyz = x(yz). 

2b) and primitive recursion has assured by the fact that all recursion equation 
admit a solution, as shown with the “from scratch” algorithm, or the algorithm 
using the “sage bird” Y.


fx0 = g(x)
fxy = h(x, f(x, py)) 

Will be given by fxy = if Zy then g(x) else h(x, f(x, py)), that is, by the 
combinator recursion equation

fxy = Zy(gx)(hx(fx(py))

Then (change of the variables) fyz = Zz(gy)(hy(fy(pz)), then there is a 
combinator A such that

Axyz = Zz(gy)(hy(xy(pz))   (f has become x)

So f = YA, by the second recursion algorithm.

The class of primitive recursive functions is a very large class of computable 
functions. Most functions encountered in applied mathematics are primitive 
recursive. So...

…subject of meditation (for “Combinator 6 (Turing Universality)):

What is missing to get a full universal programming language?

I hope you enjoy, ask *any* question. 

Note that the theory of combinators assumes only K and S, their combinations, 
and the two laws Kxy = x, and Sxyz = xz(yz).

No assumption on the existence of a physical universe has been needed, nor of 
any physical laws. (I say this to help further discussions in 

You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.

Reply via email to