All posts by chorasimilarity

Mathematics is everywhere! Open to collaborations.

You can play with the priority choice “viral”

You can download  the awk file

check_and_balance_18_09.awk

and play with chemlambda with the priority choice “viral”.

This priority choice privileges the moves which increase the number of nodes in favour of those which decrease it.

More concretely DIST>BETA>LOC-PR. It is one of the priority choices from the post When priority matters.

How to use it:

  • a g-pattern (or molecule)  is in file.mol, as a list of graphical elements (i.e. nodes with ports), but with the characters “["    "," and "]” replaced by spaces ” “. That means T[a] appears as “T a”, Arrow[a,b] appears as “Arrow a b” and L[a,b,c] appears as “L a b c”.

Look at data_8.mol , which is the file for the initial pattern from the post When priority matters. Here is also data_7.mol, which is the file containing the initial pattern from the post When priority does not matter.

  • Download the check_and_balance_18_09.awk . Download one of the data_7.mol or data_8.mol, or create your own mol file.
  • open a terminal  (presuming you have linux, or mac with Xcode installed, I suppose) and type

awk -f check_and_balance.awk data_7.mol

to play with data_7.mol. Then type ls to find a number of files, each one starting with “temp_”.

The file temp_nodes_before is basically the same as the input file.

The file temp_proposed_moves has the proposed moves :) , before any priority choice and before any COMB moves.

The file temp_final_nodes has the result after one reduction step.

You may remark the apparition of new nodes, like

FRIN 17

which is a “invisible” node which has only one port (in this case named “17”) which is an “out” port. It signals that port 17  is free (and it appears as a free “in” port, that is why FRIN, which caps it, has to have a paired “out” port).

FROUT 0

which is a invisible node with only one port (named “0” in this case) which is a “in” port. For similar reasons as before, it signals that 0 is a free “out” port.

This may change slightly the aspect of g-patterns, in the only sense that arrow elements with both ends free are replaced by  pairs FRIN and FROUT, for example if

Arrow[ 17 , 0 ]

has both ports free, you shall see it in the temp_final_nodes as

FRIN 17

FROUT 0

Otherwise the FRIN-FROUT thing helps the understanding, in the sense that it makes visible the free ports.

  • if you want to go further with the reduction then type

awk -f  check_and_balance.awk  temp_final_nodes

and look again at

temp_nodes_before   to see where you start in this reduction step

temp_proposed_moves to see the new moves proposed  before any priority choice

temp_final_nodes  to see the result.

And so on and so forth.

If you use data_7.mol or data_8.mol (or any  g-pattern from this blog which is reduced by the “viral” priority choice) then you should see exactly what is described in the respective posts.

There is a small trick, namely that when DIST moves are done, the script has a way to choose new names for the new edges which appear. The trick is that first it computes the max over existing port names ( that is the variable “tutext”) and then it baptizes the new ports with   tutext concatenated with “a”, tutext concatenated with “b”,  with “c” and with “d”.   This way one can be sure that the new ports don’t have names which conflict with the old ports.

I don’t have yet a visualizer for this, but work (mostly to understand) to use d3 for this.

Enjoy! Criticize! Contribute!

_____________________________________________________________

 

 

How space is born (0)

This opens a new series of posts, which will turn us back to the “computing with space” theme, the main interest here at chorasimilarity.

Look again at the move R2 of graphic lambda calculus.

 

r2move

The epsilon and mu are, originally, elements of a commutative group. Suggestions have been made repeatedly that the commutative group can be anything.

The epsilon and mu are port names, just like the red 1, 2, 3 from the figure.

In the more recent drawing conventions (not that that matters for the formalism) the port names are in blue.

Here is again the same move, but without the epsilon and mu.

r2_newm

Of course, the green node is the fanout, in the chemlambda version.

Yes, eventually, everything is related to everything in this open notebook.

In the next posts I shall take it step by step.

________________________________________________________________

 

 

 

 

 

 

 

 

Gold OA with CC licence, Green OA without and a lesson from the dispute between Amazon and Hachette

Further are some data along with my speculations, which may be or may be not accurate, due to my limited understanding.

Hey, everybody has a limited understanding, here is mine!

TL;DR> The crux of the matter is in this part of  any recent CC 4.0 licence: in Section 2/Scope/a. Licence grant/5.

  • “5. Downstream recipients.
    1. Offer from the Licensor – Licensed Material. Every recipient of the Licensed Material automatically receives an offer from the Licensor to exercise the Licensed Rights under the terms and conditions of this Public License.
    2. No downstream restrictions. You may not offer or impose any additional or different terms or conditions on, or apply any Effective Technological Measures to, the Licensed Material if doing so restricts exercise of the Licensed Rights by any recipient of the Licensed Material.”

 

The new trend in academic publishing is:

  • offer a CC licence for Gold OA (i.e. after the publisher has money in the pocket from the author)
  • or  offer a non-CC licence for Green OA, which does not give the protection of the boldfaced text from the CC licences.

It matters very much because that is what happens in the dispute between Amazon and Hachette, namely Hachette has the copyright of books but Amazon puts downstream restrictions!

Conclusion: never forget about Doctorow’s first law and always ask for a CC licence from any publisher!

Doctorow’s first law:

“Any time someone puts a lock on something that belongs to you, and won’t give you the key, you can be sure that the lock isn’t there for your benefit.”

This is from the very clear explanation about the Amazon and Hachette dispute by Cory Doctorow in Locus.

______________________________________________________________

Evidence now.

I made this post on G+, asking for info. I collect here the stuff:

  • In the Open letter to the AAAS about Science Advances, (new OA journal): “The default choice of a non-commercial licence (CC BY-NC) places unnecessary restrictions on reuse and does not meet the standards set out by the Budapest Open Access Initiative. Many large funders, including Research Councils UK and the Wellcome Trust, do not recognise this as an open license. The adoption of CC BY-NC as the default license means that many researchers will be unable to submit to Science Advances if they are to conform to their funder mandates unless they pay for the upgrade to CC BY. “
  • The Royal Society launches a new journal “Royal Society Open Science”. On the site of the new journal, in the section about licence to publish: they offer a licence different than CC, where they write: “4. If You decide to make the Definitive Published Version of the Article open access, this will be under a Creative Commons BY licence* [i.e. CC-BY-4.0],  You shall pay to Us the relevant fee and We shall make the Article so available from the later of the date of receipt of the relevant fee or the date of first publication of the Article.” They put  downstream restrictions for those who don’t pay them in part 6.
  • the STM new model licences, read by yourself (thanks Richard Poynder for mentioning these).

Other things:

  • the new journals of Cambridge University Press Forum of Mathematics Pi and Sigma offer only Gold OA with CC-BY-3.0, so there is no term of comparison with Green OA. (Have found this by downloading an article, nothing clear which is easy to find on their pages)
  • the new AMS journals are Gold OA, the subscription journals are Green OA.
  • the (greatest of all sites for a math or physics researcher) arXiv offers the choice between a CC-BY licence or a generic one. This is fair, because the choice is completely free left to the author.

 

UPDATE 16.09.2014: See the post AAAS vies for the title the  “Darth Vadar of publishing” by  longpd. “They  claim to support open access.  They redefine it to be a pay for publishing charge (APC)  of $3,000 USD and that restricts the subsequent use of the information in the article preventing commercial reuses such as publication on some educational blogs, incorporation into educational material, as well the use of this information by small to medium enterprises. If you really meant open access, the way the rest of world defines it, you’ll have to pay a surcharge of an additional $1,000.  But it gets worse.”

_____________________________________________________________

 

I’m doing a GUI for chemlambda

I started to work on this, here is what I am doing right now and then what I need further.

Principle. I am using the g-patterns formalism to separate the reduction of molecules from the visual representation of them.  For those who want to know more about here is the definition of g-patterns and here is the definition of moves in terms of g-patterns.

Reduction strategy. For the moment I am using a sequential strategy of reduction, with priority choices, like this:

At each reduction step do the following:

  • if no LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR are present in the g-pattern, then stop, else
  • identify the LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
  • apply the moves from LEFT to RIGHT
  • apply the COMB moves until no Arrow element
    can be eliminated
  • repeat.

There is a subtlety concerning the use of CO-COMM and CO-ASSOC moves, related to the fact that I don’t want to use them directly, and related to the goal which I have, which may be one of those:

  • use chemlambda regardless of its relation to lambda calculus (big goal). In this case there is no separation of reduction into self-multiplication and pure reduction. This strategy gets out quick, but in interesting ways, from lambda calculus, even if we start from a molecule which represents a lambda term.
  • use chemlambda for illustrating lambda calculus (small goal). In this case the reduction strategy involves a move called SHUFFLE (which is equivalent with  CO-COMM and CO-ASSOC) and a separation of the self-multiplication from pure reduction.

Where I am now. I wrote some shell scripts, using awk and perl, to do the first strategy and I know what to do to have the second strategy as well.

Mind that I learn as I do, so probably the main shell script should be named frankenstein.sh.

What I need next.  The format of g-patterns can be easily turned into a format (I lean towards json) which can be then visualized as a force directed d3 graph. I need help here, I know there are lots of things already done, the main idea is that it should be something which doesn’t use  java, has to be free, eventually has to need only the program I prepare (which will be freely available) and a browser.

What I need after.   Several things:

  • to be able to build a molecule in the window I see the graphs and to be able to convert back, to a g-pattern format. Basically this means that I need a way to add nodes which have ports, colors (red or green), such that if the node is 3valent then the cyclical order of ports is fixed. Once  added, there should be a json (say) file where the graph is saved, and then I can make a script to transform it into a g-pattern format.
  • a lambda calculus parser, which takes a lambda term (input from the user) and produces the g-pattern. See this post for the description of an algorithm which does this, starting from a lambda term  with the property that if x is a bound variable then it appears under the scope of only one abstraction and moreover it does not appear as a free variable. I can write a script which does that, but I could use something which transforms a lambda term into one which can be used in the algorithm. By extension, why not a lisp to lambda calculus convertor, which can the be plugged into the pipe of the GUI?

That’s it for the moment, I APPRECIATE  USEFUL HELP, thank you.

______________________________________________________________

 

 

When priority does not matter

Perhaps the post When priority matters gives a false impression. I want to dispel that right away.

In that post we see two possible reductions, depending on the PRIORITY CHOICE, either BETA>DIST or DIST>BETA.

In the case BETA>DIST the reduction stops quickly.

On the contrary, in the case DIST>BETA  the reduction does not stop, because it enters in a cyclic process which produces an unbounded number of bubbles (i.e. loops graphical elements).

Moreover, we start from the g-pattern form of the combinator (Lx.xx)(Lx.xx).

Or, this may lead to the false impression that somehow this has anything to do with the choice between normal order reduction and  applicative order reduction from lambda calculus.

Yes, because a standard example of the difference between these reduction strategies is the following one.

Let’s denote by Omega  the combinator (Lx.xx)(Lx.xx).  Consider then the term

(Lx.z) Omega

Under the normal order reduction this term suffers one beta reduction

(Lx.z) Omega –BETA–> z

and that’s all, the reduction stops.

 

On the contrary, under the applicative order reduction strategy, the reduction never stops, because we first try to reduce Omega, leading to a cycle

(Lx.z) Omega –BETA–> (Lx.z) Omega

 

The question is: is there any connection between these two phenomena?

  • is the sequential chemlambda reduction with BETA>DIST like normal order reduction in lambda calculus?
  • is the sequential chemlambda reduction with DIST>BETA like applicative order reduction?

No, not the slightest.

In order to prove this I shall reduce in chemlambda with the sequential strategy the g-pattern which represents the term  (Lx.z) Omega. Let’s see what happens, but first let me remind what we do.

See the 1st part and 2nd part of the description of the conversion of lambda terms into g-patterns.

The  sequential strategy is described by the following algorithm. I write it again because the g-pattern of Lx.z brings a termination node “T”, therefore we have to consider also the local pruning moves LOC-PR.

See the post about definition of moves with g-patterns.

The algorithm of the sequential reduction strategy is this. At each reduction step do the following:

  • if no LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR are present in the g-pattern, then stop, else
  • identify the LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
  • apply the moves from LEFT to RIGHT
  • apply the COMB moves until no Arrow element
    can be eliminated
  • repeat.

The PRIORITY CHOICE means a predefined choice between doing one of the two moves in conflict. The conflict may be between BETA and DIST, between  BETA and LOC-PR or between DIST and LOC-PR.

In the following we shall talk about the PRIORITY CHOICE only if needed.

In the first picture we see, in the upper side, the g-pattern which represents the term (Lx.z) Omega, then the first reduction step.

I kept the same names for the ports from the last post and I added new names for the ports of the new graphical elements.

 

n_metaloop_1

First, remark that the g-pattern which represents (Lx.z) is

L[z,n2,n1] T[n2]

I named by “z” one of the ports of the lambda node L, which would correspond to the variable z of the term Lx.z. But recall that chemlambda does not use variable names, so the name “z” is there only by my choice of names for the port variables, could be anything instead (which was not used before in one of the g-pattern’s ports).

Then, A[n1,1,0] corresponds to the application of something linked to the port n1 (namely the g-pattern of (Lx.z), i.e. L[z,n2,n1] T[n2]) to something linked to the port 1 (i.e. the g-pattern of Omega, which was discussed in the post “When priority matters”).

Nice! What happened?

  • there is an Arrow element which does not disappear, Arrow[z,0]. This is something which corresponds to the g-pattern of z, seen as lambda calculus term.
  • and there is another g-pattern, disconnected from that Arrow[z,0] graphical element.

So, in a sense, this looks like the result of the normal order reduction, but no priority choice was involved!

However, the chemlambda sequential reduction continues, like explained in the picture of the 2nd reduction step.

 

n_metaloop_2

 

 

OK, the Arrow[z,0] still exists after the reduction step, and a LOC-PR move appear.

Let’s see what happens in the 3rd reduction step.

 

n_metaloop_3

The reduction stops here. There is nothing more to do, according to the sequential reduction strategy.

Differently from the reduction of Omega alone, explained in the previous post, this time there is NO PRIORITY CHOICE NEEDED.

Ergo, the priority choice has nothing to do here. The sequential chemlambda reduction of the g-pattern corresponding to (Lx.z) Omega stops after 3 steps, no matter which was the PRIORITY CHOICE made before the start of the computation.

_________________________________________________________

 

When priority matters

I continue with the analysis of chemlambda with the very simple sequential strategy. In this post I want to show you that priority really matters, by using an old example from the Metabolism of loops.

The goal is to see how the g-pattern of the combinator

(Lx.xx) (Lx.xx)

reduces in chemlambda with the sequential strategy.

See the 1st part and 2nd part of the description of the conversion of lambda terms into g-patterns.

The simple sequential strategy is the following: at each reduction step do the following:

  • if no LEFT patterns of the moves BETA, DIST, FAN-IN are present in the g-pattern, then stop, else
  • identify the LEFT patterns of the moves BETA, DIST, FAN-IN. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
  • apply the moves from LEFT to RIGHT
  • apply the COMB moves until no Arrow element is present
    can be eliminated
  • repeat.

The PRIORITY CHOICE means a predefined choice between doing one of the two moves in conflict.

In this post it will be about the priority between BETA and DIST moves.

Mind that the PRIORITY CHOICE is fixed before the start of the computation.

However, in the following I shall mention the choice when it will be needed.

OK, so let’s start with the g-pattern which represents the well known combinator (Lx.xx) (Lx.xx).  Is clear that as a lambda term it has no normal form,  because it transforms into itself by a beta reduction (so is a sort of a quine, if quines would have an interesting definition in lambda calculus).

As previously, you shall see that we depart quickly from the lambda calculus realm, and we go to some straightforward directions, nevertheless.

The first figure describes the first reduction step.

 

metaloop_1

The g-pattern obtained after this first step is the one which appears as the starting point of the Metabolism of loops post.

The 2nd step is described in the next picture:

 

metaloop_2

Technically we are already outside lambda calculus, because of the fanin node FI[15,12,6].  (We don’t split the computation into pure reduction and pure self-multiplication.)

Let’s see the 3rd step.

 

metaloop_3

Look well at the g-pattern which we get after the 3rd step, you’ll see it again, maybe!

The 4th step is the one which will prepare the path to conflict.

 

metaloop_4

In the 5th step we have conflict:

 

metaloop_5

The 5th step finishes in a different manner, depending on the PRIORITY CHOICE (which is fixed from the beginning of the computation).

Let’s suppose that we choose DIST over BETA. Then the 5th step looks like this:

 

metaloop_6_d

Wow, the g-pattern after the 5th step is the same as the g-pattern after the 3rd step, with a loop graphical element added.

This means that further the computation will look alike the 4th step, then 5th step again (with the same priority choice, which is fixed!). A new loop will be generated and the computation will never stop, producing an endless string of loops.

Bubbles!

Now, let’s see what happens if the PRIORITY CHOICE is BETA over DIST.

Then the 5th step looks like this:

 

metaloop_6_b

The 5th step produced 2 loops and the shortest ouroboros, a fanout node with one out port connected to the in port, namely FO[13,1,13].

The computation then stops!

______________________________________________________

So, depending on the priority choice, we have either a computation which produces bubbles without end, or a computation which stops.

It is logical. Indeed, if the priority choice is DIST over BETA, this induces the choice of increasing the number of nodes of the g-pattern. From here, it may happen, as it is the case in this example, that a cyclic behaviour is induces.

On the other side, the priority choice BETA over DIST decreases the number of nodes, thus increasing the chances for a computation which stops eventually.

Both choices are good, it depends on what we want to do with them. If we want to compute with graphs resembling chemlambda quines, because they look like living organisms with a metabolism, then the choice DIST over BETA is a good one.

If we want to have a computation which stops (dies, would say a biologist) then BETA over DIST seems better.

_____________________________________________________

Quines in chemlambda

I propose the following definition of a quine, adapted to chemlambda.

In chemlambda with the sequential strategy, a quine is a g-pattern with the property that after one reduction step it transforms into another g-pattern which is the same as the initial one, up to renaming of the port variables.

Therefore: we start with a g-pattern “P”. Then

  • we identify all the LEFT g-patterns for the moves BETA, DIST, FAN-IN (see here the definition of moves)
  • in case of conflict (graphical elements appearing in two different LEFT g-patterns) we keep the g-pattern which has priority, according to a predefined priority of moves (for example DIST over BETA, or BETA over DIST,..)
  • we perform all the possible moves by changing the identified LEFT g-patterns with the RIGHT g-patterns
  • we repeat the COMB moves which serve to eliminate the Arrow elements until no Arrow element is present.

We obtain  a g-pattern, let’s call it P’.

If there is a renaming of the port variables of P’ such that, after renaming, P’ is identical with P, then P is a chemlambda quine.

Otherwise said, if P’ is identical with P as graphs, then P is a quine.

___________________________________________

Let’s think a bit: a DIST move adds 2 nodes, a BETA or a FAN-IN move remove 2 nodes, therefore, in order to hope to have a quine, we need to have the possibility to do at  least a DIST move. That means that a quine has to contain at least the RIGHT g-pattern of a DIST move. Implies that a quine must have at least 4 nodes.

A quick inspection shows that the two RIGHT g-patterns of the two DIST moves cannot be made into quines.

Therefore a quine must have at least 5 nodes. Among the nodes have to be L, A, FO, FI. But in order to reconstruct the L node and the A node one needs two DIST moves, which gives a lower bound of 8 nodes for a quine.

I believe that there is no quine with less than 9 nodes, such that the reductions never involve a choice of priority of moves.

__________________________________________

Here is now a bigger quine:

 

pred_quine

It’s a walker from the ouroboros series, walking on a circular train track with only one pair of nodes L and FO.

It has 28 nodes and 42 edges.

Can you find a smaller quine?

_________________________________________________________

UPDATE: Here is a small quine with 9 nodes and 14 edges:

 

small_quine

_________________________________________________________