Tag Archives: computation

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.


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.


Quick and dirty argument for space from chemlambda

One of the least understood ideas of chemlambda is related to this question: which is the space where these artificial molecules live?

There are two different possible applications of chemlambda, each having a different answer for this question. By confusing these two applications we arrive at the confusion about the conception of space in chemlambda.

Application 1 concerns real chemistry and biology. It is this: suppose there exist real chemical molecules which in reaction with real other substances (which play the role of the enzymes for the moves, invisible in chemlambda). Then, from the moment these real molecules and real enzymes are identified, we get *for free* a chemical computer, if we think small. If we think big, then we may hope that the real molecules are ubiquitous in biochemistry and once identified the chemical reactions which represent the chemlambda moves, then we get for free a computational interpretation of big parts of biochemistry. Thinking big, this would mean that we arrive to grasp a fundamental manifestation of computation in biochemistry, which has nothing at all to do with numbers, or bits, or boolean gates, or channels and processes, all this garbage we carry from the experience (very limited historically) we have with computation until now.

In this application 1 space is no mystery, is the well known 3d space, the vessel where real molecules roam. The interest is here not in “what is space”, but “is life in some definite clear way a computational thing?”.

Application 2 resembles more to physics than biochemistry. It aims to answer to the question what is space? Ironically from neuroscience we know that clearly living brains don’t relate with space in any way which involves coordinates and crunching numbers. However, the most fundamental physics never escaped the realm of coordinates and implicit assumptions about backgrounds.

Until now. The idea proposed by application 2 of chemlambda is that space is nothing but a sort of a program.

I try to make this clear by using emergent algebras, and will continue this path, but here is the quick and dirty argument, which appears not to use emergent algebras,  that chemlambda can explain space as a program.

(it does use them but this is a detail, pay attention to the main line.)

OK, so the artificial molecules in chemlambda are graphs. As graphs, they don’t need any space to exist, because everybody knows that a graph can be described in various ways (is a data structure) and only embeddings of a graph in a space need ahem … space.

Just graphs, encoded in .mol files, as used by the chemlambda visualiser I work on these days.

What you see on the screen when you use the visualiser is chemlambda as the main engine and some javascript salt and pepper, in order to impress our visually based monkey brains.

But, you see, chemlambda can do any computation, because it can do combinatory logic. The precise statement is that chemlambda with the reduction strategy which I call *the most stupid” is an universal computer.

That means that for any chain of reductions of a chemlambda molecule, there is another chemlambda molecule whose reductions describe the first mentioned reductions AND the javascript (and whatnot) computation which represent the said first chain of reductions on the screen.

What do you think about this bootstrapping?


The front end visual system performs like a distributed GLC computation

In this post I want to explain why the Distributed GLC  model of computation can be seen as a proof of principle that it is possible to describe rigorously some complex functioning of the brain as computation.

If you are not aware about this as being a problem, then please learn that the matter whether what brains do is computation is very controversial. On one side there are rigorous notions of computation (expressed in terms of Turing Machines, or in terms of lambda calculus, for example) which are used with full competence in CS. On the other side, in (some parts of) neuroscience the word “computation” is used in a non-rigorous sense, not because the neuroscience specialists are incapable of understanding computation in the rigorous CS sense, but because in real brains the matters are far more complex to make sense than in regards to paper  computers. Nevertheless, (some) CS specialists believe (without much real evidence) that brains compute in the CS sense, and (some) neuroscience specialists believe that their vague notions of computation deserve to bear this name, even it does not look like computation in CS rigorous sense.

OK, I shall concentrate on a particular example which I think it is extremely interesting.

In the article by Kappers, A.M.L.; Koenderink, J.J.; Doorn, A.J. van, Basic Research Series (1992), pp. 1 – 23,

Local Operations: The Embodiment of Geometry

the authors introduce the notion of  the  “Front End Visual System” . From section 1, quotes indexed by me with (1), (2), (3).

(1) Vision […]  is sustained by a dense, hierarchically nested and heterarchically juxtaposed tangle of cyclical processes.”

(2) In this chapter we focus upon the interface between the light field and those parts of the brain nearest to the transduction stage. We call this the “visual front end”.

(3) Of course, the exact limits of the interface are essentially arbitrary, but nevertheless the notion of such an interface
is valuable.


  • (2) is the definition of the front end
  • (3) is a guard against a possible entry path of the homunculus in the brain
  • (1)  has these very nice expression “dense tangle of cyclical processes”, will come back to this!

Let’s pass to the main part of interest: what does the front end?  Quotes from the section 1, indexed by me with (a), … (e):

  • (a) the front end is a “machine” in the sense of a syntactical transformer (or “signal processor”)
  • (b) there is no semantics (reference to the environment of the agent). The front end merely processes structure
  • (c) the front end is precategorical,  thus – in a way – the front end does not compute anything
  • (d) the front end operates in a bottom up fashion. Top down commands based upon semantical interpretations are not considered to be part of the front end proper
  • (e) the front end is a deterministic machine […]  all output depends causally on the (total) input from the immediate past.

Comments and reformulations, indexed by (I), … (IV)

  • (I) the front end is a syntactical transformer, it processes structure [from (a), (b)]
  • (II) there is no semantics [from (b)]; semantical interpretations are not part of the front end [from (d)]
  • (III) the front end does not compute, in the sense that there is no categorical like chasing diagrams type of computing [not formulated in terms of signals processed by gates?] [from (d)]
  • (IV) there is a clear mechanism, based on something like a “dense tangle of cyclical processes” which processes the total input (from the light field) from the immediate past [from (e) and (1)]

These (I)-(IV) are exactly the specifications of a distributed computation with GLC actors, namely:

  • a distributed, asynchronous, rigorously defined computation
  • based on local graph rewrites which are purely syntactic transformers,  a correspondent of both “dense tangle of cyclical processes” and also of “processes structure”
  • there is no semantics,  because there are no names or values which decorate the arrows of the GLC graphs, nor they travel through the nodes of such graphs. There is no evaluation procedure needed for the computation with GLC actors
  • the computation with GLC actors is done starting from an initial graph (structure) , which may use also external constructs (the cores are equivalents of the light field which triggers chemical reaction in the retina, which are then processed by the front end)

This is no coincidence! One of the reasons of building GLC was exactly the one of making sense of the front end visual system.

In conclusion:

  • yes, there is a way to rigorously describe what the front end does as computation in the CS sense, although
  • this notion of computation has some unique features: no evaluation, graph reduction based asynchronous, distributed, purely local. No semantics needed, no global notions or global controllers, neither in space, nor in time.

Neuroscience and computation: hand-in-hand

Finding the following in a CS research article:

… understanding the brain’s computing paradigm has the potential to produce a paradigm shift in current models of computing.

almost surely would qualify the respective article as crackpot, right? Wrong, for historical and contemporary reasons, which I shall mention further.

1. The cited formulation comes from the site of the Human Brain Project, one of the most amazing collaborations ever. More specifically, it is taken from here, let me cite more:

The brain differs from modern computing systems in many ways. The first striking difference is its use of heterogeneous components: unlike the components of a modern computer, the components of the brain (ion channels, receptors, synapses, neurons, circuits) are always highly diverse – a property recently shown to confer robustness to the system [1]. Second, again unlike the components of a computer, they all behave stochastically – it is never possible to predict the precise output they will produce in response to a given input; they are never “bit-precise”. Third, they can switch dynamically between communicating synchronously and asynchronously. Fourth, the way they transmit information across the brain is almost certainly very different from the way data is transmitted within a computer: each recipient neuron appears to give its own unique interpretation to the information it receives from other neurons. Finally, the brain’s hierarchically organised, massively recurrent connectively, with its small-world topology, is completely different from the interconnect architecture of any modern computer. For all these reasons, understanding the brain’s computing paradigm has the potential to produce a paradigm shift in current models of computing.

Part of the efforts made by HBP are towards neuromorphic computing.    See the presentation Real-time neuromorphic circuits for neuro-inspired computing systems by Giacomo Indiveri, in order to learn more about the history and the present of the subject.

2.  As you can see from the presentation, neuromorphic computing  is rooted in the article “A logical calculus of the ideas immanent in nervous activity” by Warren Mcculloch and Walter Pitts,1943, Bulletin of Mathematical Biophysics 5:115-133. This brings me to the “history” part. I shall use the very informative article by Gualtiero Piccinini “The First Computational Theory of Mind and Brain: A Close Look at McCulloch and Pitts’s ‘Logical Calculus of Ideas Immanent in Nervous Activity'”, Synthese 141: 175–215, 2004.  From the article:

 [p. 175] Warren S. McCulloch and Walter H. Pitt’s 1943 paper, ‘‘A Logical  Calculus of the Ideas Immanent in Nervous Activity,’’ is often cited as the starting point in neural network research. As a matter of fact,  in 1943 there already existed a lively community of biophysicists doing mathematical work on neural networks.  What was novel in McCulloch and Pitts’s paper was a theory that employed logic and the mathematical notion of computationintroduced by Alan Turing (1936–37) in terms of what came to be known as Turing  Machines – to explain how neural mechanisms might realize mental functions.

About Turing and McCulloch and Pitts:

[p. 176] The modern computational theory of mind and brain is often credited to Turing himself (e.g., by Fodor 1998). Indeed, Turing talked about the brain first as a ‘‘digital computing machine,’’ and later as a sort of analog computer.  But Turing made these statements in passing, without attempting to justify them, and he never developed a computational  theory of thinking. More importantly, Turing made these statements well after the publication of McCulloch and Pitts’s theory, which Turing knew about.  Before McCulloch and Pitts, neither Turing nor anyone else had used the mathematical notion of computation as an ingredient in a theory of mind and brain.

[p. 181] In 1936, Alan Turing published his famous paper on computability (Turing 1936–37), in which he introduced Turing Machines and used them to draw a clear and rigorous connection between computing, logic, and machinery. In particular, Turing argued that any effectively calculable function can be computed by some Turing Machine – a thesis now known as the Church–Turing thesis (CT) – and proved that some special Turing Machines, which he called ‘‘universal,’’ can compute any function computable by Turing Machines.  By the early 1940s, McCulloch had read Turing’s paper. In 1948, in a public discussion during the Hixon Symposium, McCulloch declared that in formulating his theory of mind in terms of neural mechanisms, reading Turing’s paper led him in the ‘‘right direction.’’

On McCulloch and “the logic of the nervous system”:

[p. 179] In 1929, McCulloch had a new insight. It occurred to him that the all-or-none electric impulses transmitted by each neuron to its neighbors might correspond to the mental atoms of his psychological  theory, where the relations of excitation and inhibition between neurons would perform logical operations upon electrical signals corresponding to inferences of his propositional calculus of psychons. His psychological theory of mental atoms turned into a theory of ‘‘information flowing through ranks of neurons.’’ This was McCulloch’s first attempt ‘‘to apply Boolean algebra to the behavior of nervous nets.’’ The brain would embody a logical  calculus like that of Whitehead and Russell’s Principia Mathematica, which would account for how humans could perceive objects on the basis of sensory signals and how humans could do mathematicsand abstract thinking. This was the beginning of McCulloch’s  search for the ‘‘logic of the nervous system,’’ on which he kept working until his death.

On Pitts, McCulloch and logic:

[p. 185-186] In the papers that Pitts wrote independently of McCulloch, Pitts did not suggest that the brain is a logic machine. Before McCulloch entered the picture, neither Pitts nor any  other member of Rashevsky’s biophysics group employed logical or computational language to describe the functions performed by networks of neurons. The use of logic and computation theory to model the brain and understand its function appeared for the first time in McCulloch and Pitts’s 1943 paper; this is likely to be a contribution made by McCulloch to his joint project with Pitts. […]

Soon after McCulloch met Pitts, around the end of 1941, they started collaborating on a joint mathematical theory that employed logic to model nervous activity, and they worked on it during the following two years. They worked so closely that Pitts (as well as Lettvin) moved in with McCulloch and his family for about a year in  Chicago. McCulloch and Pitts became intimate friends and they remained so until their death in 1969.  According to McCulloch, they worked largely on how to treat closed loops of activity mathematically, and the solution was worked out mostly by Pitts using techniques that McCulloch didn’t understand. To build up their formal theory, they adapted Carnap’s rigorous (but cumbersome) formalism, which Pitts knew from having studied with Carnap. Thus, according to McCulloch, Pitts did all the difficult technical work.

A citation from McCullogh and Pitts paper [p. 17 from the linked pdf]

It is easily shown: first, that every net, if furnished with a tape, scanners connected to  afferents, and suitable efferents to perform the necessary motor-operations, can compute only such numbers as can a Turing machine; second, that each of the latter numbers can be computed by such a net; and that nets with circles can be computed by such a net; and that nets with circles can compute, without scanners and a tape, some of the numbers the machine can, but no others, and not all of them. This is of interest as affording a psychological justification of the Turing definition of computability and its equivalents, Church’s  \lambda-definability and Kleene’s primitive recursiveness: If any number can be computed by an organism, it is computable by these definitions, and conversely.

Comment by Piccinini on this:

[p. 198] in discussing computation in their paper, McCulloch and Pitts  did not prove any results about the computation power of their nets;  they only stated that there were results to prove. And their conjecture was not that their nets can compute anything that can be computed by Turing Machines. Rather, they claimed that if their nets were provided with a tape, scanners, and ‘‘efferents,’’ then they would compute what Turing Machines could compute; without a tape, McCulloch and Pitts expected even nets with circles to compute a smaller class of functions than the class computable by Turing Machines.

I have boldfaced the previous paragraph because I find it especially illuminating, resembling the same kind of comment as the one on currying I gave in the post “Currying by using zippers and an allusion to the Cartesian Theater“.

[p. 198-199] McCulloch and Pitts did not explain what they meant by saying that nets compute. As far as the first part of the passage is concerned, the sense in which nets compute seems to be a matter of describing the behavior of nets by the vocabulary and formalisms of computability theory. Describing McCulloch–Pitts nets in this way turned them into a useful tool for designing circuits for computing mechanisms. This is how von Neumann would later use them (von Neumann 1945).

Ancient CS: Arbor Porphyriana

I could not resist to the title, so I started to read Umberto Eco, Dall’albero al labirinto. Studi storici sul segno e l’interpretazione (Bompiani 2007). (The brute English translation of the title is “From the tree to the labyrinth. Historical Studies on  sign and  interpretation “.) Just opening the book, I learned about Arbor Porphyriana.

I shall cite from the very rough description given in the wiki page (before, let me laugh a bit by reading from the talk page of the mentioned wiki page: “This article has been rated as Low-importance on the project’s importance scale.” Ha-ha, an encyclopedia to state that arbor porphyriana is a low importance subject, that’s weird. Is like the egg stating that chickens are not important on it’s scale.)

The Porphyrian tree, Tree of Porphyry or Arbor Porphyriana is a classic classification of a “Scale of being”,[1] invented by one of the earliest Greek logicians Porphyry.[2] It is also known as scala praedicamentalis.

The Greek Neoplatonist Porphyry introduced the Porphyrian tree in his introduction to Aristotle‘s Categories. Porphyry presented the basis of Aristotle’s thought as a tree-like scheme of dichotomous divisions, which indicates that a species is defined by genus-differentia and that the process continues until the lowest species is reached.

This work was translated into Latin by Boethius and became the standard philosophical textbook in the Middle Ages.[3] Until the late 19th century, it was still being taught to students of logic.

So, that’s a huge subject. A short google search for “arbor porphyriana ontology semantic web” gives on the first place these very interesting slides by Harald Sack: “Semantic Web Technologies“.

Animals in lambda calculus II. The monoid structure and patterns

This is a continuation of “Animals in lambda calculus“. You may need to consult the web tutorial on graphic lambda calculus.

Animals are particular graphs in GRAPH. They were introduced in the mentioned post. I wrote there that animals have the meaning of a kind of transformations over terms in lambda calculus. I shall come back to this at the end of this post and a future post will develop this subject.

The anatomy of an animal is described in the next figure.


The animal has therefore a body, which is a graph in GRAPH with only one output, decorated in the figure with “OUT”.  The allowed gates in the body are: the \lambda gate, the \curlywedge gate, the termination and the \Upsilon gates.

To the body is grafted a \Upsilon tree, with the root decorated in the figure with “IN”. The said tree is called “the spine” of the animal and the grafting points are called “insertions” and are figured by green small disks in the figure.

An animal may have a trivial spine (no \Upsilon gate, only a wire). The most trivial animal is the wire itself, with the body containing just a wire and with no insertion points. Let’s call this animal “the identity”.

Animals may compose one with another, simply by grafting the “OUT” of one animal to the “IN” of the other. The body, the spine and the insertions of the composed animal are described in the next figure.


The moral is that the spine and the insertions  of the composed animal are inherited from the first animal in the composition, excepting the case when the first animal has trivial spine (not depicted in the figure).

The pleasant thing is that the set of animals is a monoid with composition and with the identity animal as neutral element. That is: the composition of animals is associative and the identity is the neutral element.

In the first post about animals it is explained that the graphic beta move transforms an animal into an animal.  Indeed, the animal


is transformed into the animal


The graphic beta move goes in both directions.  For example the identity animal is transformed by the graphic beta move into the following animal


With this monoid structure in mind, we may ask if there is any category structure behind, such that the animals are (decorations of) arrows. Otherwise said, is there any interesting category which admits a functor from it to the monoid of animals, seen as a category with one object and animals as arrows?

An interesting category is the one of “patterns”, the subject will be developed in a future post. But here I shall explain, in a not totally rigorous way,  what a pattern is.

The category of patterns has the untyped lambda terms as objects (with some care about the use of alpha equivalence) and patterns as arrows. A category may be defined only in terms of its arrows, therefore let me say what a pattern should be.

A bit loosely speaking, a pattern is a pair (A[u:=B], B), where A,B are untyped lambda calculus terms and u is a variable. I call it a pattern because really it is one. Namely, start from the following data: a term A, a variable u (which appears in A … ) and another term B. They generate a new term A[u:=B] which has all the occurences of the term B in A[u:=B] which were caused by the substitution u:=B, marked somehow.

If you think a bit in graphic lambda terms, that is almost an animal with the “IN” decorated by B and the “OUT” decorated by A[u:=B].

Composition of animals corresponds to composition of patterns, namely (C[v:= A[u:=B]], A[u:=B]) (A[u:=B], B) = (D[u:=B], B), where D is a term which is defined (with care) such that D[u:=B] = C[v:= A[u:=B]].

Clearly, the definition of patterns ant their composition is not at all rigorous, but it will be made so in a future post.