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.


These pacman macros are used for defining the Ackermann machine:


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.


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:


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.



5 thoughts on “A machine for computing the Ackermann function in graphic lambda calculus”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s