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. 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 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 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) 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. OK, but please reread the thread combinator 2 which explains in details the 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 to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
