# Combinator 6 (Turing Universality, the Mu operator)

```Hi,

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.

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
combinator.

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
course)
= 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
point:

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
combinators.
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

The general case, or a more general case is, when G and H are two primitive

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)

Thus

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

And

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

So

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

And so YF’ gives the combinator computing that F.

OK?

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
functions.

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
itself.

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).

Done.

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

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

And

(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).

Done.

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

algorithm:

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))

Vérification:
S(S(KS)A)(K(KB))xy =
S(KS)Ax(K(KB)x)y =
KSx(Ax)(KB)y =
S(Ax)(KB)y =
Axy(KBy) =
AxyB
checked!

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
computations.

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.

Bruno

(*) ============= 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
functions).
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
class.)
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.

OK?

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.

Typically

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
metaphysics/theology).

--
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