What reduction is this?

It ends in the Church encoding of 2.

Can you guess what is this? (click on the big image to see it better)

 

pred_1

 

As you see, you may ask:

  • what kind of evaluation strategy is this?
  • are there reduction steps and self-multiplication steps?
  • is this in lambda calculus?
  • what can we learn from this particular example?

_______________________________________________

 

Y again: conclusion!

In the post Y again: conflict! I took the most obvious reduction strategy (sequential) and applied it to the reduction of the “Y combinator applied to something”.  The reduction ended in conflict between two moves which compete for the same g-pattern.

Then, in the post Y again:compete!  I took in parallel the two possible outcomes of the conflict. The contenders have been branded as fast shooting cowboys, offering a show.

Surprisingly, both possible paths of reduction ended in a very simple version of the Y combinator.

Only  that the very simple version is not one coming from lambda calculus!

Indeed, let’s recall who is the Y combinator, seen a g-pattern in chemlambda.

In lambda calculus the Y combinator is

Lx.( (Ly.(x(yy)) (Ly.(x(yy)) )

As a molecule, it looks like this.

 

yagain_2

As g-pattern, it looks like this (see this post  and this post for the conversion of lambda terms into g-patterns):

L[a,x,o] A[b,c,a] FO[x,y,z]

L[e,d,b] FO[d,f,g] A[f,g,h] A[y,h,e]

L[j,i,c] FO[i,l,m] A[l,m,k] A[z,k,j]

 

Applied to something means we add to this g-pattern  the following:

A[o,p,u]

with the meaning that Y applies to whatever links to the port “p”. (But mind that in chemlambda there is no variable or term passing or evaluation! so this is a way to speak in the lambda calculus realm, only).

The two mentioned posts about Y again led to the conclusion that the g-pattern “Y applied to something” behaves (eventually, after several reductions) as the far more simple g-pattern:

A[o,p,u]                (i.e. “applied to something at port “p”)

L[b,a,o]

FO[a,c,d] A[c,d,b]

Now, this means that the Y combinator g-pattern may be safely replaced in computations by

L[b,a,o]

FO[a,c,d] A[c,d,b]

or, in graphical version, by

 

yagain_5

But this is outside lambda calculus.

So what?

It is far simpler than the Y combinator from lambda calculus.

The same happens with other lambda terms and reductions.(see for example the post Actors for the Ackermann machine, for another example. Incidentally, the analysis of the Ackermann machine, i.e. the graph which behaves like the Ackermann function, gave me the idea of using the actor model with GLC. This evolved into arXiv:1312.4333.).

This shows  the fact that chemlambda, even with the dumbest sequential reduction strategy (ok, enhanced in obvious ways so it solves conflicts), can do more with less fuss than lambda calculus.

By looking on the net (recall that I’m a mathematician, therefore excuse my ignorance in CS well known people, I’m working on this), I can’t but wonder what chemlambda would give in relation with, for example:

Of course, the dream is to go much, much further. Why? Because of  the List of Ayes/Noes of the artificial chemistry chemlambda.

__________________________________________________________

 

Y again: compete!

In the post Y again: conflict!  the chemlambda computation based on a very crude model ended in conflict.

Conflict means that the same graphical element appears in two LEFT g-patterns (see, in the series of expository posts  the part II for the g-patterns and the part III for the moves) .

In the next figure we see this conflict, in the upper part (that’s where we were left in the previous post), followed by a fork: in the lower left part of the figure we see what we get if we apply the beta move and in the lower right part we see what happens if we apply the DIST move.

 

yagain_3

 

Recall that (or look again at the upper side of the picture) the conflict was between LEFT patterns of a beta move and of a DIST move.

I rearranged the drawing of the g-patterns a bit (mind that this is not affecting in any way the graphs, because the drawings on paper or screen are one thing and the graphs another thing, excuse me for being trivially obvious). In this pretty picture we see well that already the Y gun shot a second pair of nodes A and FO.

The differences now:

  • for the graph from the lower left part of the picture, obtained after the beta move, we see that A[i.i] produces a loop: A[i,i] –COMB–> loop. We can disregard the loop further (because we allow only moves from LEFT to RIGHT, therefore the loop will not interact with anything in the future of the computation). We are left with a very simple graph, made of the two pairs of nodes A and FO which the gun already shot and with a very interesting pair:  A[w,a1,o] FO[o,q,a1] .
  • for the graph from the lower right part of the picture, obtained after the DIST move, we see the two pairs of nodes A and FO whih the Y gun already shot and a graph made by 6 nodes.

Which way is the best? What to do?

Let’s make them compete!  Who shoots faster?

 

Imagine the scene: in the Lambda Saloon, somewhere in the Wide Wild West, enter two new cowboys.

“Who called these guys?” asks the sheriff of the Functional City, where the reputed saloon resides.

“They are strangers! They both look like Lucky Luke, though…”

The cowboys and cowgirls from the saloon nod in approval: they all remember what happened when Lucky Luke — the one, the single cowboy who shoots faster than his shadow — was put between the two parallel mirrors from the saloon stage. What a show! That day, the Functional City got a reputation, and everybody knows that reputation is something as good as gold. Let the merchants from Imperative County sell windows panes for the whole US, nobody   messes with a cowboy, or cowgirl from the Functional City. Small, but elegant. Yes sir, style is the right word…

Let’s go back to the two strangers.

“I’m faster than Master Y” says the stranger from the right.

“I’m MUCH faster than Master Y” says the one from the left, releasing from his cigar a loop of smoke.

“Who the … is Master Y?” asks the sheriff.

“Why, it’s Lucky Luke. He trained us both, then sent us to Functional City. He says hello to you and tells you that he got new tricks to show” says one of the strangers.

“… things not learned from church…” says the other.

“I need to see how fast are you, or else I call you both liars” shouts one of the bearded, long haired  cowboys.

The stranger from the right started first. What a show!

 

yagain_right

He first makes a clever DIST move (not that there was anything else to do). Then he is presented with 4 simultaneous moves to do (FAN-IN, 2 betas and a DIST). He shoots and freezes. Nothing moves, excepting two loops of smoke, rising from his gun.

“I could continue like this forever, but I stopped, to let my colleague show you what he’s good at.” said the stranger from the right.

“Anyway, I am a bit slow  with the first shot, but after that I am faster.” he continued.

“Wait, said the sheriff, you sure you really shot?”

“Yep, sure, look better how I stand”, said the stranger from the right, only slightly modifying his posture, so that everybody could clearly see the shot:

 

yagain_right_2

“Wow, true!” said the cowboys.

“I’m fast from the first shoot!” said the stranger from the left. “Look!”

 

yagain_left

“I only did a DIST move.” said the stranger from the left, freezing in his posture.

“Nice show, guys! Hey, look, I can’t tell now which is which, they look the same. I got it, the guy from the right is a bit slower at the first shoot (however he is dazzlingly fast) but then he is as  good as his fellow from the left.”

“Hm, said the sheriff, true. Only one thing: I have never seen in the Lambda Saloon  anything like this. It’s fast, but it does not seem to belong here.”

___________________________________________________________

Y again: conflict!

We proved in    arXiv:1403.8046 [cs.AI]  ( link to the published  article) that in chemlambda the molecule which represents the Y combinator is a gun which shoots pairs of FO and A nodes. See there the sequence of reductions which was considered.

This time  let’s not care about staying in lambda calculus and let’s take the simplest reduction strategy, to see what happens.

We posit in the frame of g-patterns from the expository posts  part I  and part II (definition of g-patterns) and part III (definition of moves) and part IV (g-patterns for lambda terms 1st part) and part V (g-patterns for lambda terms 2nd part) and part VI (about self-multiplication of g-patterns)  and part VII (an example of reduction) .

We take the following reduction strategy:

  • we start with a g-pattern and we reduce it sequentially
  • at each step we identify first all the LEFT patterns from the following moves: beta, DIST, FAN-IN,
  • we do the moves from LEFT to RIGHT
  • we identify and do all possible COMB moves from LEFT to RIGHT
  • repeat until no move available OR until conflict.

What’s conflict? We shall see one.

Mind that this is a very stupid and simplistic strategy, which does not guarantee that if we start with a g-pattern which represents a lambda term then we stop by having a g-pattern of a lambda term.

It does have it’s advantages, though.

OK, so let us start with the g-pattern of Y applied to something. 

In general, with g-patterns we can say many things. As any combinator molecule, when represented by a g-pattern, the Y combinator has only one free port, let’s call it “b”. Thus Y appears as a g-pattern which we denote by Y[b].

Suppose we want to tart the reduction from Y applied to something. This means that we shall start with the g-pattern

A[b,a,out] Y[b]

OK!

Look what happens when we apply the mentioned strategy.

(Advice: big picture, click on it to see it clearly and to travel along it.)

 

yagain_1

Here is a conflict: at one step we have two LEFT patterns, in this case

L[o,p,i] A[i,p,v]   , which is good for a beta move

and

A[i.p.v] FO[v,q,a1]  , which is good for a DIST move.

The patterns contain a common graphical element, in this case A[i,p,v], which will be deleted during the respective moves.

CONCLUSION: with this strategy we have a gun which shoots one pair of FO and A nodes, but then it got wrecked.

What to do then?

The human way is to apply

When in trouble or in doubt

Run in circles, scream and shout

for a moment, then acknowledge that this is a stupid reduction strategy, then find some qualities of this strategy, then propose another which has those qualities but works better, then reformulate the whole problem and give it an unexpected turn.

The AI way is to wait for somebody to change the reduction strategy.

__________________________________________________________

Github laudatio: negative Coase cost

This is a record of a mind changing experience I had with Github, one which will manifest in the months to come. (Well, it’s time to move on, to move further, new experiences await, I like to do this…)

Here is not more than what is in this ephemeral google+ post, but is enough to get the idea.

And it’s controversial, although obvious.

“I  just got hooked by github.io . Has everything, is a dream came true. Publishing? arXiv? pfff…. I know, everybody knows this already, let me enjoy the thought, for the moment. Then it will be some action.

 
Continuing with github and publishing, this is a worthy subject (although I believe that practically github already dwarfed legacy publishing, academia and arXiv). Here is an excerpt from a post from 2011
http://marciovm.com/i-want-a-github-of-science/
 
“- Publishing is central to Academia, but its publishing system is outclassed by what Open Source software developers have in GitHub

- GitHub’s success is not just about openness, but also a prestige economy that rewards valuable content producers with credit and attention

-Open Science efforts like arXiv and PLoS ONE should follow GitHub’s lead and embrace the social web”

I am aware about the many efforts about publishing via github, I only wonder if that’s not like putting a horse in front of a rocket.

On the other side, there is so much to do, now that I feel I’ve seen rock solid proof that academia, publishing and all that jazz is walking dead, with the last drops of arterial blood splatting around from the headless body. “

 

Negative Coase cost?

__________________________________________________

 

Lambda calculus and the fixed point combinator in chemlambda (VIII)

This is the 8th  (continuing from part I  and part II  and part III and part IV and part V and part VI  and part VII) in a series of expository posts where we put together in one place the pieces from various places about:

  • how is treated lambda calculus in chemlambda
  • how it works, with special emphasis on the fixed point combinator.

I hope to make this presentation  self-contained. (However, look up this page, there are links to online tutorials, as well as already many posts on the general subjects, which you may discover either by clicking on the tag cloud at left, or by searching by keywords in this open notebook.)

_________________________________________________________

This series of posts may be used as a longer, more detailed version of sections

  • The chemlambda formalism
  • Chemlambda and lambda calculus
  • Propagators, distributors, multipliers and guns
  • The Y combinator and self-multiplication

from the article M. Buliga, L.H. Kauffman, Chemlambda, universality and self-multiplication,  arXiv:1403.8046 [cs.AI],  presented  by Louis Kauffman in the ALIFE 14 conference, 7/30 to 8/2 – 2014 – Javits Center / SUNY Global Center – New York.  Here is a link to the published  article, free, at MIT Press.

_________________________________________________________

Tags. I shall use the name “tag” instead of “actor” or “type”, because is more generic (and because in future developments we shall talk  more about actors and types, continuing from the post Actors as types in the beta move, tentative).

Every port of a graphical element (see part II)  and the graphical element itself can have tags, denoted by :tagname.

There is a null tag “null” which can be omitted in the g-patterns.

As an example, we may see, in the most ornate way, graphical elements like this one:

L[x:a,y:b,z:c]:d

where of course

L[x:null,y:null,z:null]:null    means L[x,y,z]

The port names are tags, in particular “in” out” “middle” “left” and “right” are tags.

Any concatenation of tags is a tag.  Concatenation of tags is denoted by a dot, for example “left.right.null.left.in”.  By the use of “null” we have

a.null –concat–> a

null.a –concat–> a

I shall not regard concat as a move in itself (maybe I should, but that is for later).

Further in this post I shall not use tags for nodes.

Moves with tags. We can use tags in the moves, according to a predefined convention. I shall take several  examples.

1. The FAN-IN move with tags. If the tags a and b are different then

FI[x:a, y:b, z:c] FO[z:c,u:b, v:a]

–FAN-IN–>

Arrow[x:a,v:a] Arrow[y:b,u:b]

Remark that the move is not reversible.

It means that you can do FAN-IN only if the right tags are there.

2. COMB with tags.

L[x:a, y:b, z:c] Arrow[y:b, u:d]

–COMB–>

L[x:a, u:d,z:c]

and so on for all the comb moves which involve two graphical elements.

3. DIST with tags.  There are two DIST moves, here with tags.

A[x:a,y:b,z:c] FO[z:c,u:d,v:e]

–DIST–>

FO[x:a, w:left.d, p:right.e]   FO[y:b, s:left.d, t:right.e]

A[w:left.d, s:left.d, u:d]   A[p:right.e, t:right.e, v:e]

In graphical version

 

dist_with_tags

 

and the DIST move for the L node:

L[y:b, x:a, z:c] FO[z:c, u:d, v:e]

–DIST–>

FI[p:right, w:left, x:a] FO[y:b, s:left, t:right]

L[s:left, w:left,u:d]  L[t:right, p:right, v:e]

In graphical version:

 

dist_tags_lambda

 4. SHUFFLE. This move replaces CO-ASSOC, CO-COMM. (It can be done as a sequence of CO-COMM and CO-ASSOC; conversely, CO-COMM and CO-ASSOC can be done by SHUFFLE and LOC PRUNING, explanations another time.)

FO[x:a, y:b, z:c]  FO[y:b, w:left, p:right] FO[z:c, s:left, t:right]

–SHUFFLE–>

FO[x:a, y:left, z:right]  FO[y:left, w, s] FO[z:right, p, t]

In graphical version:

 

shuffle_with.tags

 

____________________________________________________________

 

 

 

A symplectic Brezis-Ekeland-Nayroles principle

We submitted to the arXiv the article

Marius Buliga, Gery de Saxce, A symplectic Brezis-Ekeland-Nayroles principle

You can find here the slides of two talks given in Lille and Paris a while ago,  where the article has been announced.

UPDATE: The article appeared, as  arXiv:1408.3102

This is, we hope, an important article! Here is why.

The Brezis-Ekeland-Nayroles principle appeared in two articles from 1976, the first by Brezis-Ekeland, the second by Nayroles. These articles appeared too early, compared to the computation power of the time!

We call the principle by the initials of the names of the inventors: the BEN principle.

The BEN principle asserts that the curve of evolution of a elasto-plastic body minimizes a certain functional, among all possible evolution curves which are compatible with the initial and boundary conditions.

This opens the possibility to find, at once the evolution curve, instead of constructing it incrementally with respect to time.

In 1976 this was SF for the computers of the moment. Now it’s the right time!

Pay attention to the fact that a continuous mechanics system has states belonging to an infinite dimensional space (i.e. has an infinite number of degrees of freedom), therefore we almost never hope to find, nor need the exact solution of the evolution problem. We are happy for all practical purposes with approximate solutions.

We are not after the exact evolution curve, instead we are looking for an approximate evolution curve which has the right quantitative approximate properties, and all the right qualitative exact properties.

In elasto-plasticity (a hugely important class of materials for engineering applications) the evolution equations are moreover not smooth. Differential calculus is conveniently and beautifully replaced by convex analysis.

Another aspect is that elasto-plastic materials are dissipative, therefore there is no obvious hope to treat them with the tools of hamiltonian mechanics.

Our symplectic BEN principle does this: one principle covers the dynamical, dissipative evolution of a body, in a way which can be reasonably easy amenable to numerical applications.

_______________________________________

 

computing with space | open notebook

computing with space | open notebook

cemerick

Against all odds.

The Quilt Project

writings on data, communication, and computation

Low Dimensional Topology

Recent Progress and Open Problems

Towards a 2nd Renaissance

The Internet of Things & Services: Renaissance Re-Born

kauffman2013

A fine WordPress.com site

Voxel-Engine

An expirimental non-gpu 3d voxel engine.

Theory, Evolution, and Games Group

The EGG studies theoretical computer science, evolution, and game theory.

semanto.me

freedom to grok

outfind.ca *

Out think, out search, out find * A blog by Olivier Charbonneau, Business Librarian at Concordia University (Montréal)

Sauropod Vertebra Picture of the Week

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

isomorphismes

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

Shtetl-Optimized

computing with space | open notebook

Theoretical Atlas

He had bought a large map representing the sea, / Without the least vestige of land: / And the crew were much pleased when they found it to be / A map they could all understand.

Gödel's Lost Letter and P=NP

a personal view of the theory of computation

Gowers's Weblog

Mathematics related discussions

Research and Lecture notes

by Fabrice Baudoin

The "Putnam Program"

Language & Brains, Machines & Minds

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Follow

Get every new post delivered to your Inbox.

Join 80 other followers

%d bloggers like this: