Tag Archives: Ackermann function

Summer news, Ackermann related observations and things to come

Light summer post, want more then follow the links.

1. after a chemlambda demo appeared on hackernews  (link) I saw a lot of interest from hacker brains (hopefully). Even if slightly misplaced (title reads: D3.js visualization of a lambda calculus) it is an entry gate into this fascinating subject.

2. Sreejith S (aka 4lhc) works on a python port for chemlambda, called chemlambda-py. It works already, I look forward to try it when back home. Thank you Sreejith! Follow his effort and, why not, contribute?

3. Herman Bergwerf set out to write a chemlambda IDE, another great initiative which I am very eager to see it working, just by looking at Herman beautiful MolView.

4. During discussions with Sreejith, I noticed some funny facts about the way chemlambda computes the Ackermann function. Some preliminaries: without cheats (i.e. closed forms) or without memoization, caching, etc, it is hopeless to try to compute Ack(4,2). The problem is not as much the fact that the function takes huge values, but the fact that in order to compute even modest values, there are lots and lots of calls. See the rosettacode entry for the Ackermann function about that. Compared with those examples, the implementation of chemlambda in awk does not behave bad at all. There are now several mol files for various ackermann function values which you may try. The only one which takes lots of time (but not huge memory, if you except the html output, which you can eliminate by commenting with a # all printf lines in the awk script) is ackermann_4_1. `This one works, but I still have to see how much time it takes. The interesting observation is that the number of steps (in the deterministic version) of chemlambda (mind: steps not rewrites!) is at 1 or 2 difference than the number of steps of this beautiful stacks based script: ackermann script. It means that somehow the chemlambda version records in space the intermediary values, instead of stacking them for further use. Very strange, to explore!

5. There exist, on paper, the chemlambda v3 “enzo”. It’s very very nice, you’ll see!

Advertisements

Experiments with a little lisper tutorial

I used the excellent lambda calculus tutorial by Mayer Goldberg from the little-lisper.org for some experiments in chemlambda.

UPDATE: See also the post The working factorial and the video

_______________

There are five of them.

The mentioned tutorial is the source for the lambda term which I translated into chemlambda and then used in the Ackermann function demos. The most outrageously successful is the computation of Ack(2,2) while self-multiplicating. The daughter molecules do not end at the same time, moreover.

Here is a video of a screen recording at 2X speed.

Now, there is a very puzzling thing here. In chemlambda with a random, purely local graph rewriting algorithm I can compute the Ackermann function. But what about simpler functions, like the factorial?

I tried the easy way consisting into translation of lambda terms for the factorial into chemlambda and the results are ugly. As a geometer who wants to decipher computation without using variables, values, variable passing or evaluations, I know that chemlambda is different because of this feature it has: it uses something like signal transduction instead of gates-and-wires general model from IT. So there has to be consequences of that.

Let’s see what happens in the case of the factorial. In this demo I took the lambda term from the same tutorial, par. 57, page 14. I hoped will work better than other proposals, based on the experience with the Ackermann function. I noticed in other experiments with terms for the factorial that the reduction in chemlambda is extremely wasteful, producing thousands of nodes and lots of trash. Moreover, there is a problem with the fix point combinator, explained in the article with Louis Kauffman Chemlambda, universality and self multiplication, and described in the older demos like this one. In chemlambda, the molecule which corresponds to the Y combinator reduces to a very simple one (which does not has an equivalent as a lambda term), made by only two nodes, fanout and application. Then the molecule becomes a gun which shoots pairs of fanout and application node. There is no mystery about the Y combinator in chemlambda, the real mechanism of it consists in the self-multiplication by the fanout node. [Note: in the old demo and in the article linked there is no FOE fanout. The FOE and the moves associated to it are a recent addition to the formalism, see the page of moves.]

The problem of using the Y combinator is that it never stops generating pairs of A and FOE nodes. In a computation which implements recurrence by the Y combinator, at some point, according to a IFTHENELSE or ISZERO, the cycle of Y is broken. But in chemlambda the Y gun molecule continues to exist and this leads to a never ending computation. From one side this is OK, see for example the life-like computations with chemlambda quines. Actually there is a stronger relation between chemlambda quines and the Y combinator molecule. One can design the computation to be such that when the Y molecule is no longer needed, it is encapsulated into a quine, but this is for another time to explain in detail.

I come back to the factorial example. In the demo I linked you can see that the computation of the factorial is wasteful (and paradoxically leads to a Y molecule), even if it does not use a fix point combinator.

Why?

First I thought it is because of currying and uncurrying. In chemlambda, because it is a graph rewrite system, there is no particular need to use currying all the time.

Then, to check this, I modified the molecule from the little lisper tutorial in order to geometrically compute the repeated application of a function f(a,b)=(succ(a), succ(a)b). The function is a piece of a graph with two in and two out links which is self-multiplying under the action of a number in the Church encoding.

Here is a successful computation with this molecule. But does it work all the time or have I been lucky? The reduction algorithm is random and different runs may give different results. It is the case with the Ackermann function computation as well, but that one was successful all the time.

Oh, it turns out that the computation with that molecule works well in about 20% of the runs. Here is an unsuccessful run.

So there is still a problem, but which one?

Under close examination the computation is still wasteful, because of the term (piece of molecule) c0, for the 0 in the Church encoding. In chemlambda this term corresponds to a small molecule which has a termination node inside.

When we want to thrash, like programmers do, something useless, in chemlambda the useless piece does not disappear. Is like in nature, the thing continues to exist and continues to interact, while in the process of degradation, with the rest of the environment.

The termination node, via the PRUNING moves, destroys slowly the useless part, but pother pieces form the useless part continue to interact with the rest of the graph.

Is this the problem?

In order to check this I further modified the molecule which was successful 20% of the time. I just replaced c0 by c1, which is the (molecule for) the lambda term for 1 in the Church encoding. Now, c1 does not have any termination node inside.

The price is that I no longer compute the factorial, but instead I compute the repeatedly applied function

F(a,b)=(succ(a), tms(a,b))

where tms(a,b)=ab+1. Here is a demo for the computation of tms(3,3) in chemlambda., and further is a video for tms(5,5)=26, where you can see a new creature, more complex than the walker discover in the predecessor.

I checked to see what is the closed expression, if any, for the function I compute, namely

f(0)=1, f(n+1) = (n+1)f(n) + 1

and the Wolfram Alpha engine has an interesting answer.

Well, this time I hit the right spot. The computation works, again and again and again.

So we have to learn to program ecologically with chemlambda.

____________________________________________________________________

Dynamic rendering of the Ackermann function computation, deterministical and random

Source code here.

This video contains two examples of the computation of the Ackermann function by using artificial chemistry. The (graph rewriting) rules are those of chemlambda and there are two models of computation using them.


In the first one the rules are applied deterministically, in the order of their importance. The rules which increase the number of nodes are considered more important than those which decrease the number of nodes. The rules are applied in parallel, as long as there is no conflict (i.e. as long as they don’t apply to the same node). When there is conflict the rule with higher importance takes the priority.
In the first part of the video you see what happens if this model is applied to a graph which represents (according to the rules of chemlambda) the Ackermann function applied to (2,2). The expected result is 7 (as it appears in the Church encoding, which is then transformed in the chemlambda convention). There are no tricks, like pre-computing the expression of the function, everything goes at a very basic level. The application of the rules does not parallel the application of lambda calculus reduction rules to the lambda term which represents the Ack(2,2), with any reduction strategy. However, the result is obtained correctly, even if many of the intermediary steps are not graphs which represent a lambda term.

 

The model does not use any variable passing, nor any evaluation strategy, moreover!

In the second example is used a different model of computation. The rules are applied randomly. That means the following. For any configuration from the graph which may be subject to a rule, a coin is flipped and the rule is applied with probability 50%. The rules are equally important. The rules are still applied in parallel, in the sense that an update on the graph is done after all edges are visited.

As you see in the second part of the video, the process takes longer, because essentially at each step there are always less rules applied to the whole graph. The comparison is not very accurate, because the reduction process may depend on the particular run of the program. Even if lambda beta calculus (with some model of reduction) is confluent, chemlambda is surely not. It is an open problem if, starting from a graph which represents a lambda term, in chemlambda, knowing that in lambda calculus the term has a normal form, then the random model of computation with chemlambda always arrives eventually to the graph which represents the normal form of the respective term.
At least for the term I use here for Ack(2,2), it looks like that it does. This is of course not a proof.

 

UPDATE: A quine is reduced in chemlambda, first using a deterministic model of computation then using a model which has a random ingredient.


These two models are the same as the ones used for the Ackermann function video.
The quine is called the 9_quine, has been introduced in https://chorasimilarity.wordpress.com/…

In the deterministic reduction you see that at each step the graph reduces and reconstruct itself. It goes on forever like that.

In the random reduction the process is different. In fact, if you look at the list of reductions suffered by the 9_quine, then you see that after each cycle of reduction (in the deterministic version) the graph is isomorphic with the one before because there is an equilibrium between the rules which add nodes and the rules which destroy nodes.
In the random version this equilibrium is broken, therefore you see how the graph grows either by having more and more red nodes, or by having more and more green nodes.
However, because each rule is applied with equal probability, in the long term the graph veers towards a dominant green or towards dominant red states, from one to the other, endlessly.
This is proof that the reductions in chemlambda vary according to the order of application of moves. On the other side, this is evidence (but not proof) that there is a sort of fair effort towards eventual confluence. I use “confluence” in a vague manner, not related to lambda calculus (because the 9_quine does not come from a lambda term), but more related to the graph rewriting world.

_________________________________________________________________________

The Ackermann function in the chemlambda gui

UPDATE: The Ackermann function, the video:

_______________________

I put this stuff on G+  some days ago and now I can find it only if I look for it on purpose. Older and newer posts, those I can see. I can see colored lobsters, funny nerd jokes, propaganda pro and con legacy publishing, propaganda hidden behind granpa’s way of communicating science, half baked philosophical ideas,  but not my post which I made only two days ago. On my page, I mean, not elsewhere.

Thank you G+ for this, once again. (Note not for humans: this was ironic.)  Don’t forget to draw another box next time when you think about a new algorithm.

A non-ironic thanks though for the very rare occasions when I did met very interesting people and very interesting ideas there.

OK, to the matter, now. But really, G+, what kind of algorithm you use which keeps a lobster on my page but deletes a post about the Ackermann function?

UPDATE: The post is back in sight now. Whew!
The post follows, slightly edited (by adding stuff).
The Ackermann function is an example of a total computable function which is not primitive recursive. It is therefore amusing to try to compute it.
The matter is not what is the value of Ack(m,n), because it grows so fast that very soon the problem of computing it is shadowed by the more trivial problem of storing its values. Instead,  more interesting is to see how your computing device handles the computation itself, things like stacks of calls, etc, because here it is manifest the fact that Ack is not primitive recursive.
To simplify it, the funny thing is to see how you can compute Ack(m,n) without any cheat.
I tried to do this with #chemlambda . I know since a long time that it can be done, as explained (very summary, true) in this old post
https://chorasimilarity.wordpress.com/2013/10/19/a-machine-for-computing-the-ackermann-function-in-graphic-lambda-calculus/
for GLC, not chemlambda (but since chemlambda does with only local moves what GLC does, it’s the same).
I want to show you some pictures about it.
It is about computing Ack(3,2). Everybody will point that Ack(3,2) = 29 and moreover that Ack(3,n) has an explicit expression, but this would be cheating, because I don’t want to use precomputed stuff.
No, what I want to use is a lambda calculus term for the Ackermann function (and one which is not eta reduced, because chemlambda does not have eta reduction!), and I want to apply it to the arguments 3 and 2 written as lambda terms as well (using the Church encoding). Then I want to see if after the reductions performed by the algorithm I have I get 29 as a Church number as well.
During all the algorithm I use only graph reductions!
After all there are no calls, no functions and during the computation the molecules which appear are not even representing lambda terms.
Indeed, lambda calculus does not have operations or concepts like fanin nodes, or FOE nodes, not reductions like FAN-IN or DIST. That’s the amazing point (or at least one of them), that even if it veers outside lambda calculus, it ends where it should (or better, that’s for another time).
I used the programs which are available at the site of the chemlambda gui http://imar.ro/~mbuliga/gallery.html
(which is btw online again, after 2 days of server corruption.)Here are some pictures.The first one is a screenshot of the Ack(3,2) “molecule”, i.e. the graph which is to be reduced according to the chemlambda rules and according to the reduction strategy which I call “viral”.
ack_3_2_init
After almost 200 reductions I get 29, see the second figure, where it appears as the molecule which represents 29 as a Church numeral.
ack_3_2_finalWow, it really worked!
You can try it for yourself, I’ll give you the mol file to play with, but first some details about it.
I modified a bit the awk script which does the reductions, in the following place: when it introduces new nodes (after a DIST move) it has to invent new names for the new edges. In the script which is available for download the algorithm takes the max over all all ports names and concatenate it with a word which describes where the edge comes from. It is good for being able to track back where the nodes and edges come, but it results into a growth of the ports name which is exponential in the number of iterations of the reduction algorithm. This leads to very big names of some ports, after 200 iterations.
So I modified this part by choosing a naming procedure which is less helpful for tracking but better in the sense that now the growth of names is linear in the number of iterations. It is a quick fix, after all it is as easy to invent naming procedures which result in a logarithmic or almost constant length wrt the number of iterations.
For the Ackermann function the script which is available is just as good, it works well, only that it has this unpleasant feature of long names which enlarges unnecessarily the json files.
Details over, next now.
In the third picture you see the mol file for the Ack(3,2), i.e. the list of nodes and ports of the Ack(3,2) molecule, in the format used by the reduction program.
ack_3_2_mol
Btw, do you see in this screenshot the name of the updated script? Right, is foe_bubbles_09_10.awk, instead of foe_bubbles_06_10.awk which is available for download.
I don’t cheat at all, see?
I made some annotations which helps you to see which part corresponds to the Ackermann function (as a lambda term translated into chemlamda), which parts are the arguments “3” and “2”, and finally which part represents the Ackermann function applied to (3,2).
ackermann_3_2_mol
Soon enough, when I’ll be able to show you animated reductions (instead of the steps of reduction only), I think such an example will be very funny to examine, as it grows and then shrinks back to the result.
________________________________________

 

 

 

Actors for the Ackermann machine (II) Pure communication.

Continues from Actors for the Ackermann machine . In this post we see the first interaction between the actors.

Notations: each actor a has an address :a and a stack a^{*}.

Let the play begin. The cast is the following:

ack_7

At the beginning of the performance, the actors are in the following configuration

ack_8

Only a with b can interact (i.e. the only moves in GLC which may happen between actors are those between the mentioned ones). Their interaction is a form of pure communication (via the graphic beta move). Two such moves are possible, in succession. This is described in the next figure, along with the changes in the actors configuration.

ack_9

The performance is thrilling: the actor a is almost exhausted after forcing  the actor b to drop down his mask.  In the process  a lost his friends  d and f (with his buddy e) in favour of b.  Only c is still taking the side of a.   What will happen next?

At this stage, no other interaction is possible without revealing what b is really thinking (what’s in his stack b^{*}). The first act is over.

_________________________

Actors for the Ackermann machine

Continues A machine for computing the Ackermann function in graphic lambda calculus , by a preliminary analysis of the proposed Ackermann machine in GLC from the Actor Model point of view.

ack_6

Very brief notes:

  • see Hewitt Actor Model, lambda calculus and graphic lambda calculus   for the actor notation (or decoration)
  • binary fission is an apt name for the replacement of the GLOBAL FAN-OUT from GLC by the DIST moves from chemlambda (because eventually I am interested in using the purely local formalism of chemlambda for the Ackermann machine).
  • “mask” is a new name instead of the “pacman” name used in the first post on the Ackermann machine.
  • “stack” might correspond to the “mailbox” in the actor model, but it’s internal to the actor and interacts only with the mask.

All this has a working hypothesis basis, I’m thinking out loud – btw, if you look then  you can also talk here 🙂 . Everything is subject to changes, remember this is an open notebook (which can also be cited as explained at the right side of the post).

________________________

A machine for computing the Ackermann function in graphic lambda calculus

The Ackermann function is a computable function which is not primitive recursive. It can be expressed in untyped lambda beta  calculus (which is the version that I use).

UPDATE (April 2015): see the much better demos for this in chemlambda, like Ackermann(2,2)=7 computation. It is moreover random and the pet example for a proof of principle experiment with a hypothetical molecular computer.

Let’s see how does it look in graphic lambda calculus. I shall explain how the computation of it unfolds in at least one more post. In this one I shall concentrate at defining a sort of machine which does the computation of this function.

Very, briefly, I introduce some macros (i.e. notations) for the relevant pieces which are used in this Ackermann machine.

ack_1

These pacman macros are used for defining the Ackermann machine:

ack_2

Some explanations and remarks are in order.

1. As you see, the Ackermann machine looks like a pacman munching pacmans, some of them controlled by other pacmans.

2. The Ackermann machine as presented here is not the graph obtained from the lambda calculus term which represents the Ackermann function (explanations in a future post).

3. The coloured rectangles can be any graph in GRAPH with two entries and two exits. Depending on what these graphs are, the Ackermann machine does different things, one of them being the computation of the Ackermann function. The fact that such graphs are taken with two entries and two exits is reminiscent of the modelling of B-type neural networks with graphic lambda calculus, where synapses are also such graphs (this needs more explanations, are for later).

4. In particular, the coloured rectangles can be chosen in a way related to the Church encoding of the numerals. Indeed, look at the following figure, which contains examples of graphs which can be used as the coloured rectangles in the Ackermann machine.

ack_3

It’s clear what they are: a kind of stacks which accumulate copies of the same “elementary unit”, or otherwise they are empty (i.e. the first graph). I use these to obtain the Church numerals:

ack_5

5. The same can be done with the chemical concrete machine, of course. This observation is relevant because the way the machine functions (by local graph rewrites), when expressed in the chemical concrete machine formalism, will look like a chemical reaction network.

____________________________