Busy beaver’s random church

The demo linked here would surely look impossible.

One computer, WHILE IT WORKS, is multiplied into 3 computers which  continue to work, each of them. This feat is done without any higher control and there are never conflicts which appear. All computers work asynchronously (mimicked here by randomness). Moreover, eventually they arrive to read and write on the same tape.

There are no calls, nothing you have seen before.Everything is local, no matter how you slice it into separated parts.


OMG the busy beaver goes into abstract thinking

So called higher capacities, like abstraction, are highly hyped.  Look:
What happens when you apply the Church number 3 to a busy beaver? You get 3 busy beavers on the same tape.

Details will be added into the article Turing machines, chemlambda style.

If you want tot experiment, then click on “fork me on github” and copy the gh-pages branch of the repo. Then look in the dynamic folder for the script moving_random_metabo_bb.sh. In a terminal type “bash moving_random_metabo_bb.sh”, then type “church3bb.mol”. You shall get the file church3bb.html which you can see by using a js enabled browser.
The sh script calls an awk script, which produces the html file. The awk script is check_1_mov2_rand_metabo_bb.awk. Open it with a text editor and you shall see at the beginning all kinds of parameters which you can change (before calling the sh script), so that you may alter the duration, the speed, change between deterministic and random algorithms.
Finally, you also need a mol file to play. For this demo has been used the mol file church3bb.mol. You can also open it with a text editor and play with it.

UPDATE: Will tweak it more the next days, but the idea which I want to communicate is that TM can be seen as chemistry, like in chemlambda, and it can interact very well with the rest of the formalism. So you have these two pillars of computation on the same footing, together, despite the impression that they are somehow very different, one like hardware and the other like software.


Turing Machines, chemlambda style (I)

UPDATE: First animation and a more detailed version here. There will be many additions, as well as programs available from the gh-pages of the repo.

Once again: why do chemists try to reproduce silicon computers? Because that’s the movie.

    At first sight they look very different. Therefore, if we want to compare them, we have to reformulate them in ways which are similar. Rewrite systems are appropriate here.
    The Turing Machine (TM) is a model of computation which is well-known as being a formalisation of what a computer is. It is a machine which has some internal states (from a set S), has a head which read/writes symbols (from a set A) on a tape. The tape is seen as an infinite word made of letters from A. The set A has a special letter (call it “b” from blank) and the infinite words which describe tapes have to be such that all but a finite number of letters of that word are different from “b”. Imagine an infinite, in both directions, tape which has written symbols on it, such that “b” represents an empty space. The tape has only a finite part of it filled with letters from A, others than the blank letter.
    The action of the machine depends on the internal state and on the symbol read by the head. It is therefore a function of the internal state of the machine (element of S), the letter from the tape which is read (element of A), and outputs a letter from the alphabet A (which is written in the case where previously was the letter which has been read, changes its internal state, and the head moves one step along the tape, to the left (L) or right (R), or does not move at all (N).
    The TM can be seen as a rewrite system.
    For example, one could see a TM as follows. (Pedantically this is seen as a multi-headed TM without internal states; the only interest in this distinction is that it raises the question if there is really any meaning into discerning internal states from the tape symbols.) We start from a set (or type) of internal states S. Such states are denoted by A, B, C (thus exhibiting their type by the type of the font used). There are 3 special symbols: < is the symbol of the beginning of a list (i.e. word), > is the symbol of the end of a list (word) and M is the special symbol for the head move (or of the type associated to head moves). There is an alphabet A of external states (i.e. tape symbols), with b (the blank) being in A.
    A tape is then a finite word (list) of one of the forms < w A w’ > , < w M A w’ > , < w A M w’ >, where A is an internal state and w and w’ are finite words written with the alphabet A, which can be empty words as well.
    A rewrite replaces a left pattern (LT) by a right pattern (RT), and there are denoted as LT – – > RT . Here LT and RT are sub-words of the tape word. It supposed that all rewrites are context independent, i.e. LT is replaced by RT regardless of the place where LT appears in the tape word. The rewrite is called “local” if the lengths (i.e. number of letters) of LT and RT are bounded a priori.
    A TM is given as a list of Turing instructions, which have the form (current internal state, tape letter read, new internal state, tape letter write, move of the tape). In terms as explained here, all this can be expressed via local rewrites.

  • Rewrites which introduce blanks at the extremities of the written tape:
    • < A   – – >   < b A
    • A >   – – >   A b >
  • Rewrites which describe how the head moves:
    • A M a   – – >   a A
    • a M A   – – >   A a
  • Turing instructions rewrites:
    • a A c   – – >   d B M c   , for the Turing instruction (A, a, B, d, R)
    • a A c   – – >   d M B c   , for the Turing instruction (A, a, B, d, L)
    • a A c   – – >   d B c   , for the Turing instruction (A, a, B, d, N)
    Together with the algorithm “at each step apply all the rewrites which are possible, else stop” we obtain the deterministic TM model of computation. For any initial tape word, the algorithm explains what the TM does to that tape. < don’t forget to link that to a part of the Cartesian method “to be sure that I made an exhaustive enumeration” which is clearly going down today > Other algorithms are of course possible. Before mentioning some very simple variants of the basic algorithm, let’s see when it works.
    If we start from a tape word as defined here, there is never a conflict of rewrites. This means that there is never the case that two LT from two different rewrites overlap. It might be the case though, if we formulate some rewrites a bit differently. For example, suppose that the Turing rewrites are modified to:
  • a A   – – >   d B M   , for the Turing instruction (A, a, B, d, R)
  • a A   – – >   d M B   , for the Turing instruction (A, a, B, d, L)
    Therefore, the LT of the Turing rewrites is no longer of the form “a A c”, but of the form “a A”. Then it may enter in conflict with the other rewrites, like in the cases:

  • a A M c where two overlapping rewrites are possible
    • Turing rewrite: a A M c   – – >   d M B M c &nbsp which will later produce two possibilities for the head moves rewrites, due to the string M B M
    • head moves rewrite: a A M c   – – >   a c A &nbsp which then produces a LT for a Turing rewrite for c A, instead of the previous Turing rewrite for a A
  • a A > where one may apply a Turing rewrite on a A, or a blank rewrite on A >
    The list is non exhaustive. Let’s turn back to the initial formulation to the Turing rewrites and instead let’s change the definition of a tape word. For example, suppose we allow multiple TM heads on the same tape, more precisely suppose that we accept initial tape words of the form < w1 A w2 B w3 C … wN >. Then we shall surely encounter conflicts between head moves rewrites for patterns as a A M B c.
    The most simple solution for solving these conflicts is to introduce a priority of rewrites. For example we may impose that blank rewrites take precedence over head moves rewrites, which take precedence over Turing rewrites. More such structure can be imposed (like some head moves rewrites have precedence over others). Even new rewrites may be introduced, for example rewrites which allow multiple TMs on the same tape to switch place.
    Let’s see an example: the 2-symbols, 3-states

busy beaver machine

    . Following the conventions from this work, the tape letters (i.e. the alphabet A) are “b” and “1”, the internal states are A, B, C, HALT. (The state HALT may get special treatment, but this is not mandatory). The rewrites are:

  • Rewrites which introduce blanks at the extremities of the written tape:
    • < X   – – >   < b X   for every internal state X
    • A >   – – >   A b >   for every internal state X
  • Rewrites which describe how the head moves:
    • X M a   – – >   a X   , for every internal state X and every tape letter a
    • a M X   – – >   X a   , for every internal state X and every tape letter a
  • Turing instructions rewrites:
    • b A c   – – >   1 B M c   , for every tape letter c
    • b B c   – – >   b C M c   , for every tape letter c
    • b C c   – – >   1 M C c   , for every tape letter c
    • 1 A c   – – >   1 HALT M c   , for every tape letter c
    • 1 B c   – – >   1 B M c   , for every tape letter c
    • 1 C c   – – >   1 M A c   , for every tape letter c
    We can enhance this by adding the priority of rewrites, for example in the previous list, any rewrite has priority over the rewrites written below it. In this way we may relax the definition of the initial tape word and allow for multiple heads on the same tape. Or for multiple tapes.
    Suppose we put the machine to work with an infinite tape with all symbols being blanks. This corresponds to the tape word < A >. Further are the steps of the computation:
  • < A >   – – >   < b A >
  • <b A >   – – >   < b A b >
  • < b A b >   – – >   < 1 B M b >
  • < 1 B M b >   – – >   < 1 b B >
  • < 1 b B >   – – >   < 1 b B b >
  • < 1 b B b >   – – >   < 1 b C M b >
  • < 1 b C M b >   – – >   < 1 b b C >
  • < 1 b b C >   – – >   < 1 b b C b >
  • < 1 b b C b >   – – >   < 1 b 1 M C b >
  • < 1 b 1 M C b >   – – >   < 1 b C 1 b >
  • < 1 b C 1 b >   – – >   < 1 1 M C 1 b >
  • < 1 1 M C 1 b >   – – >   < 1 C 1 1 b >
  • < 1 C 1 1 b >   – – >   < 1 M A 1 1 b >
  • < 1 M A 1 1 b >   – – >   < A 1 1 1 b >
  • < A 1 1 1 b >   – – >   < b A 1 1 1 b >
  • < b A 1 1 1 b >   – – >   < 1 B M 1 1 1 b >
  • <1 B M 1 1 1 b >   – – >   < 1 1 B 1 1 b >
  • < 1 1 B 1 1 b >   – – >   < 1 1 B M 1 1 b >
  • < 1 1 B M 1 1 b >   – – >   < 1 1 1 B 1 b >
  • < 1 1 1 B 1 b >   – – >   < 1 1 1 B M 1 b >
  • < 1 1 1 B M 1 b >   – – >   < 1 1 1 1 B b >
  • < 1 1 1 1 B b >   – – >   < 1 1 1 1 B M b >
  • < 1 1 1 1 B M b >   – – >   < 1 1 1 1 b B >
  • < 1 1 1 1 b B >   – – >   < 1 1 1 1 b B b >
  • < 1 1 1 1 b B b >   – – >   < 1 1 1 1 b C M b >
  • < 1 1 1 1 b C M b >   – – >   < 1 1 1 1 b b C >
  • < 1 1 1 1 b b C >   – – >   < 1 1 1 1 b b C b >
  • < 1 1 1 1 b b C b >   – – >   < 1 1 1 1 b 1 M C b >
  • < 1 1 1 1 b 1 M C b >   – – >   < 1 1 1 1 b C 1 b >
  • < 1 1 1 1 b C 1 b >   – – >   < 1 1 1 1 1 M C 1 b >
  • < 1 1 1 1 1 M C 1 b >   – – >   < 1 1 1 1 C 1 1 b >
  • < 1 1 1 1 C 1 1 b >   – – >   < 1 1 1 1 M A 1 1 b >
  • < 1 1 1 1 M A 1 1 b >   – – >   < 1 1 1 A 1 1 1 b >
  • < 1 1 1 A 1 1 1 b >   – – >   < 1 1 1 HALT M 1 1 1 b >
  • < 1 1 1 HALT M 1 1 1 b >   – – >   < 1 1 1 1 HALT 1 1 b >
    At this stage there are no possible rewrites. Otherwise said, the computation stops. Remark that the priority of rewrites imposed a path of the rewrites applications. Also, at each step there was only one rewrite possible, even if the algorithm does not ask for this.
    More possibilities appear if we see the tape words as graphs. In this case we pass from rewrites to graph rewrites. Here is a proposal for this.
    I shall use the same kind of notation as in

chemlambda: the mol format

    . It goes like this, explained for the busy beaver TM example. We have 9 symbols, which can be seen as nodes in a graph:

  • < which is a node with one “out” port. Use the notation FRIN out
  • > which is a node with one “in” port. Use the notation FROUT in
  • b, 1, A, B, C, HALT, M which are nodes with one “in” and one”out” port. Use a notation Name of node in out
    The rule is to connect “in” ports with “out” ports, in order to obtain a tape word. Or a tape graph, with many busy beavers on it. (TO BE CONTINUED…)

Reproducibility vs peer review

Here are my thoughts about replacing peer review by validation. Peer review is the practice where the work of a researcher is commented by peers. The content of the commentaries (reviews) is clearly not important. The social practice is to not make them public, nor to keep a public record about those. The only purpose of peer review is to signal that at least one, two, three or four members of the professional community (peers) declare that they believe that the said work is valid. Validation by reproducibility is much more than this peer review practice. Validation means the following:

  • a researcher makes public (i.e. “publishes”) a body of work, call it W. The work contains text, links, video, databases, experiments, anything. By making it public, the work is claimed to be valid, provided that the external resources used (as other works, for example) are valid. In itself, validation has no meaning.
  • a second part (anybody)  can also publish a validation assessment of the work W. The validation assessment is a body of work as well, and thus is potentially submitted to the same validation practices described here. In particular, by publishing the validation assessment, call it W1, it is also claimed to be valid, provided the external resources (other works used, excepting W) are valid.
  • the validation assessment W1 makes claims of the following kind: provided that external works A,B,C are valid, then this piece D of the work W is valid because it has been reproduced in the work W1. Alternatively, under the same hypothesis about the external work, in the work W1 is claimed that the other piece E of the work D cannot be reproduced in the same.
  • the means for reproducibility have to be provided by each work. They can be proofs, programs, experimental data.

As you can see the validation can be only relative, not absolute. I am sure that scientific results are never amenable to an acyclic graph of validations by reproducibility. Compared to peer review, which is only a social claim that somebody from the guild checked it, validation through reproducibility is much more, even if it does not provide means to absolute truths. What is preferable: to have a social claim that something is true, or to have a body of works where “relative truth” dependencies are exposed? This is moreover technically possible, in principle. However, this is not easy to do, at least because:

  • traditional means of publication and its practices are based on social validation (peer review)
  • there is this illusion that there is somehow an absolute semantical categorification of knowledge, pushed forward by those who are technically able to implement a validation reproducibility scheme at a large scale.

UPDATE: The mentioned illusion is related to outdated parts of the cartesian method. It is therefore a manifestation of the “cartesian disease”.

I use further the post More on the cartesian method and it’s associated disease. In that post the cartesian method is parsed like this:

  • (1a) “never to accept anything for true which I did not clearly know to be such”
  • (1b) “to comprise nothing more in my judgement than what was presented to my mind”
  • (1c) “so clearly and distinctly as to exclude all ground of doubt”
  • (2a) “to divide each of the difficulties under examination into as many parts as possible”
  • (2b) “and as might be necessary for its adequate solution”
  • (3a) “to conduct my thoughts in such order that”
  • (3b) “by commencing with objects the simplest and easiest to know, I might ascend […] to the knowledge of the more complex”
  • (3c) “little and little, and, as it were, step by step”
  • (3d) “assigning in thought a certain order even to those objects which in their own nature do not stand in a relation of antecedence and sequence”

Let’s take several researchers who produce works, some works related to others, as explained in the validation procedure.

Differently from the time of Descartes, there are plenty of researchers who think in the same time, and moreover the body of works they produce is huge.

Every piece of the cartesian method has to be considered relative to each researcher and this is what causes many problems.

Parts (1a),(1b), (1c) can be seen as part of the validation technique, but with the condition to see “true”and “exclude all grounds of doubt” as relative to the reproducibility of work W1 by a reader who tries to validate it up to external resources.

Parts (2a), (2b) are clearly researcher dependent; in a interconnected world these parts may introduce far more complexity than the original research work W1.

Combined with (1c), this leads to the illusion that the algorithm which embodies the cartesian method, when run in a decentralized and asynchronous world of users, HALTS.

There is no ground for that.

But the most damaging is (3d). First, every researcher embeds a piece of work into a narrative in order to explain the work. There is nothing “objective” about that. In a connected world, with the help of Google and alike, who impose or seek for global coherence, the parts (3d) and (2a), (2b) transform the cartesian method into a global echo chamber. The management of work bloats and spill over the work itself and in the same time the cartesian method always HALT, but for no scientific reason at all.


Inflation created by the Curry’s paradox

Curry’s paradox expressed in lambda calculus.

I took the lambda term from there and I modified slightly the part which describes the IFTHEN (figured by an arrow in the wiki explanation)

IFTHEN a b  appears in chemlambda as

A 1 a2 out
A a1 b 1
FO a a1 a2

which if you think a little bit, behaves like IFTHENELSE a b a.

Once I built a term like the “r” from the wiki explanation, instead of  using rr, I made a graph by the following procedure:

– take the graph of r applied to something (i.e. suppose that the free out port of r is “1” then add A 1 in out)

– make a copy of that graph (i.e in mol notation duplicate the mol file of the previous graph, change the ports variable — here by adding the “a” postfix)

– then apply one to the other (i.e. modify

A 1 in out
A 1a ina outa


A 1 outa out,
A 1a out outa)

The initial mol file is:

A 1 outa out
A 1a out outa

L 2 3 1
A 4 7 2
A 6 5 4
FO 8 6 7

FO 3 9 10
A 9 10 8

L 2a 3a 1a
A 4a 7a 2a
A 6a 5a 4a
FO 8a 6a 7a

FO 3a 9a 10a
A 9a 10a 8a

The parameters are: cycounter=8; wei_FOFOE=0; wei_LFOELFO=0; wei_AFOAFOE=0; wei_FIFO=0; wei_FIFOE=0; wei_AL=0;

i.e is a deterministic run for 8 steps.

Done in chemlambda.


A citizen science project on autonomous computing molecules

 Wanted: chemists, or people who work(ed) with chemical molecules databases!
[update:  github.io version]
The  chemlambda project proposes the following. Chemlambda is a model of computation based on individual molecules, which compute alone, by themselves (in a certain well defined sense). Everything is formulated from the point of view of ONE molecule which interacts randomly with a family of enzymes.
So what?
Bad detail: chemlambda is not a real chemistry, it’s artificial.
Good detail: it is Turing universal in a very powerful sense. It does not rely on boolean gates kind of computation, but on the other pillar of computation which led to functional programming: lambda calculus.
So instead of molecular assemblies which mimic a silicon computer hardware, chemlambda can do sophisticated programming stuff with chemical reactions. (The idea that lambda calculus is a sort of chemistry appeared in the ALCHEMY (i.e. algorithmic chemistry) proposal by Fontana and Buss. Chemlambda is far more concrete and simple than Alchemy, principially different, but it nevertheless owes to Alchemy the idea that lambda calculus can be done chemically.)
From here,  the following reasoning.
(a) Suppose we can make this chemistry real, as explained in the article Molecular computers.  This looks reasonable, based on the extreme simplicity of chemlambda reactions. The citizen science part is essential for this step.
(b) Then is is possible to take further Craig Venter’s Digital Biological Converters (which already exist) idea and enhance it to the point of being able to “print” autonomous computing molecules. Which can do anything (amenable to a computation, so literary anything). Anything in the sense that they can do it alone, once printed.
The first step of such an ambitious project is a very modest one: identify the ingredients in real chemistry.
The second step would be to recreate with real chemistry some of the examples which have been already shown as working, such as the factorial, or the Ackermann function.
Already this second step would be a huge advance over the actual state of the art in molecular computing. Indeed, compare a handful of boolean gates with a functional programming like computation.
If it is, for example, a big deal to build with DNA some simple assemblies of boolean gates, then surely it is a bigger deal to be able to compute the Ackermann function (which is not primitive recursive, like the factorial) as the result of a random chemical process acting on individual molecules.
It looks perfect for a citizen science project, because what is missing is a human distributed search in existing databases, combined with a call for realization of possibly simple proofs of principles chemical experiments based on an existing simple and rigorous formalism.
Once these two steps are realized, then the proof of principle part ends and more practical directions open.
Nobody wants to compute factorials with chemistry, silicon computers are much better for this task. Instead, chemical tiny computers as described here are good for something else.
If you examine what happens in this chemical computation, then you realize that it is in fact a means towards self-building of chemical or geometrical structure at the molecular level. The chemlambda computations are not done by numbers, or bits, but by structure processing. Or this structure processing is the real goal!
Universal structure processing!
In the chemlambda vision page this is taken even further, towards the interaction with the future Internet of Things.

Biological teleportation taken further

The idea is simple. Put these together:


Craig Venter’s Digital Biological Converter

which could print autonomous computing  molecules.

That’s more than just teleportation.

Suppose you want to do anything in the real world. You can design a microscopic molecular computer for that, by using chemlambda. Send it by the web to a DBC like device. Print it. Plant it. Watch it doing the job.






computing with space | open notebook


computing with space | open notebook


News from coreboot world

Chemoton § Vitorino Ramos' research notebook

Random thoughts and works around Artificial Life & Intelligence, Bio-inspired Computation, Complex Sciences, their Applications, Technology, Science, Culture and Society

Steve Grand's Blog

Artificial Life in real life


computing with space | open notebook

Not Even Wrong

computing with space | open notebook

Random thoughts and fancy math

computing with space | open notebook


The Decentralised Internet is Here

The future of scientific publishing

ideas for an open, transparent, independent system


Lets live and learn

An Exercise in Irrelevance

Knowledge, Biology and Ontologies


computing with space | open notebook

Low Dimensional Topology

Recent Progress and Open Problems


An expirimental non-gpu 3d voxel engine.

Sauropod Vertebra Picture of the Week

SV-POW! ... All sauropod vertebrae, except when we're talking about Open Access


computing with space | open notebook

DIANABUJA'S BLOG: Africa, The Middle East, Agriculture, History and Culture

Ambling through the present and past with thoughts about the future

Retraction Watch

Tracking retractions as a window into the scientific process

Gödel's Lost Letter and P=NP

a personal view of the theory of computation

The "Putnam Program"

Language & Brains, Machines & Minds


Get every new post delivered to your Inbox.

Join 123 other followers

%d bloggers like this: