From the wiki page of Combinatory logic:

Combinatory logicis a notation to eliminate the need for variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based oncombinators.

For the treatment of combinators in graphic lambda calculus see section 3.1 of Local and global moves on locally planar trivalent graphs, lambda calculus and lambda-Scale, arxiv:1207.0332.

In this post I want to discuss about the conversion of the lambda calculus sector of the graphic lambda calculus formalism into the knot diagram sector plus * stickers*.

There are two stickers, they are graphs in $GRAPH$ with the following form:

I call them “stickers” because they behave like devices which concentrate the attention at the region encircled by the closed loop. Think about a sticker with nothing written on it. This is a thing which you can stick in some place and you can write something on it. Likewise, take any graph in $GRAPH$ with a marked OUT leaf (for any example take any combinator in graphic lambda calculus form, which always has an unique OUT leaf) and connect it with one of the stickers (i.e. “write it on the sticker”). The operation analoguous to sticking the written sticker on something is to cross the sticker connected with a combinator with another combinator, where “crossing” refers to the knot diagrams sector, with its graphic lambda crossings.

Look how the stickers behave:

They may be converted one into another (by way of graphic beta moves). Moreover, they transform the application operation gate into a crossing!

Let us see the behaviour of some combinators connected with stickers. Take the combinator . In the next figure, we see it in the upper left corner, in graphic lambda formalism. (The figure has two layers. One may read only what is written in black, considering after what happens if the red drawings are added.)

In black, we see that the graph of connected with a sticker transforms by a graphic beta move into a loop. If we add the red part, we see that the graph transforms into a loop with a crossing with a graph . If we perform a second graphic beta move (in red) then we get . This corresponds to the combinatory logic relation .

Likewise, let’s consider the combinator , with associated graph described in the left upper corner of the next figure.

With the added red part, it corresponds to the relation with a fresh variable for .

I skip the combinator for a future discussion, but from this post it looks almost clear that by using stickers we may convert the combinatory logic sector of the graphic lambda calculus into the knot diagrams sector enhanced with stickers and maybe with zippers (but we shall see that we may eliminate one or another, in some sense).

## 2 thoughts on “Combinators and stickers”