## Graphic lambda calculus
Marius Buliga
Institute of Mathematics, Romanian Academy P.O. BOX 1-764, RO 014700 Bucure¸ sti, Romania
Marius.Buliga@imar.ro
This version: 23.05.2013
## Abstract
We introduce and study graphic lambda calculus, a visual language which can be used for representing untyped lambda calculus, but it can also be used for computations in emergent algebras or for representing Reidemeister moves of locally planar tangle diagrams.
## 1 Introduction
Graphic lambda calculus consists of a class of graphs endowed with moves between them. It might be considered a visual language in the sense of Erwig [9]. The name 'graphic lambda calculus' comes from the fact that it can be used for representing terms and reductions from untyped lambda calculus. It's main move is called 'graphic beta move' for it's relation to the beta reduction in lambda calculus. However, the graphic beta move can be applied outside the 'sector' of untyped lambda calculus, and the graphic lambda calculus can be used for other purposes than the one of visual representing lambda calculus.
For other visual, diagrammatic representation of lambda calculus see the VEX language [8], or David Keenan's [15].
The motivation for introducing graphic lambda calculus comes from the study of emergent algebras. In fact, my goal is to build eventually a logic system which can be used for the formalization of certain 'computations' in emergent algebras, which can be applied then for a discrete differential calculus which exists for metric spaces with dilations, comprising riemannian manifolds and sub-riemannian spaces with very low regularity.
Emergent algebras are a generalization of quandles, namely an emergent algebra is a family of idempotent right quasigroups indexed by the elements of an abelian group, while quandles are self-distributive idempotent right quasigroups. Tangle diagrams decorated by quandles or racks are a well known tool in knot theory [10] [13].
It is notable to mention the work of Kauffman [14], where the author uses knot diagrams for representing combinatory logic, thus untyped lambda calculus. Also Meredith and Snyder[17] associate to any knot diagram a process in pi-calculus,
Is there any common ground between these three apparently separated field, namely differential calculus, logic and tangle diagrams? As a first attempt for understanding this, I proposed λ -Scale calculus [5], which is a formalism which contains both untyped lambda calculus and emergent algebras. Also, in the paper [6] I proposed a formalism of decorated tangle diagrams for emergent algebras and I called 'computing with space' the various manipulations of these diagrams with geometric content. Nevertheless, in that paper I was not able to give a precise sense of the use of the word 'computing'. I speculated, by using analogies from studies of the visual system, especially the 'Brain a geometry engine' paradigm of Koenderink [16], that, in order for the visual front end of the brain to reconstruct the visual space in the brain, there should be a kind of 'geometrical computation' in the
neural network of the brain akin to the manipulation of decorated tangle diagrams described in our paper.
I hope to convince the reader that graphic lambda calculus gives a rigorous answer to this question, being a formalism which contains, in a sense, lambda calculus, emergent algebras and tangle diagrams formalisms.
Acknowledgement. This work was supported by a grant of the Romanian National Authority for Scientific Research, CNCS UEFISCDI, project number PN-II-ID-PCE-2011-30383.
## 2 Graphs and moves
An oriented graph is a pair ( V, E ), with V the set of nodes and E ⊂ V × V the set of edges. Let us denote by α : V → 2 E the map which associates to any node N ∈ V the set of adjacent edges α ( N ). In this paper we work with locally planar graphs with decorated nodes, i.e. we shall attach to a graph ( V, E ) supplementary information:
- -a function f : V → A which associates to any node N ∈ V an element of the 'graphical alphabet' A (see definition 2.1),
- -a cyclic order of α ( N ) for any N ∈ V , which is equivalent to giving a local embedding of the node N and edges adjacent to it into the plane.
We shall construct a set of locally planar graphs with decorated nodes, starting from a graphical alphabet of elementary graphs. On the set of graphs we shall define local transformations, or moves. Global moves or conditions will be then introduced.
Definition 2.1 The graphical alphabet contains the elementary graphs, or gates, denoted by λ , Υ , , , and for any element ε of the commutative group Γ , a graph denoted by ¯ ε . Here are the elements of the graphical alphabet:
<details>
<summary>Image 1 Details</summary>
### Visual Description
## Diagram: Graph Representations
### Overview
The image presents a series of diagrams representing different types of graphs, each labeled with a Greek letter and the word "graph". Each graph consists of a central node (represented by a circle containing a Greek letter or symbol) connected to edges represented by arrows.
### Components/Axes
* **Nodes:** Each graph has a central node enclosed in a circle. The circles contain the following symbols: λ, ƛ, Υ, ε.
* **Edges:** Each node is connected to three edges, except for the last graph, which has only one edge. The edges are represented by arrows, indicating direction.
* **Labels:** Each graph is labeled with a Greek letter or symbol followed by the word "graph". The labels are: λ graph, ƛ graph, Υ graph, ε graph, ⊥ graph.
### Detailed Analysis or ### Content Details
The image contains five distinct graph representations, arranged in two rows and one single graph in the third row.
* **Row 1:**
* **Graph 1 (top-left):** A circle containing the Greek letter "λ" with three arrows connected to it. Two arrows point away from the circle at approximately 45-degree angles, and one arrow points towards the circle from below. The label is "λ graph".
* **Graph 2 (top-right):** A circle containing the Greek letter "Υ" with three arrows connected to it. Two arrows point away from the circle at approximately 45-degree angles, and one arrow points towards the circle from below. The label is "Υ graph".
* **Row 2:**
* **Graph 3 (bottom-left):** A circle containing the symbol "ƛ" with three arrows connected to it. Two arrows point away from the circle at approximately 45-degree angles, and one arrow points towards the circle from below. The label is "ƛ graph".
* **Graph 4 (bottom-right):** A circle containing the Greek letter "ε" with three arrows connected to it. Two arrows point away from the circle at approximately 45-degree angles, and one arrow points towards the circle from below. The label is "ε graph".
* **Row 3:**
* **Graph 5 (bottom-center):** A horizontal line with one arrow pointing downwards. The label is "⊥ graph".
### Key Observations
* All graphs, except the last one, have a similar structure with a central node and three connecting edges.
* The arrows indicate the direction of the edges, suggesting a flow or relationship between the nodes.
* The Greek letters and symbols within the circles likely represent different types or states of the nodes.
### Interpretation
The image illustrates different graph representations, possibly used in a mathematical or computational context. The variations in the central node's symbol and the direction of the edges suggest different types of relationships or operations within the graph. The "⊥ graph" appears to be a special case, possibly representing a terminal state or a grounding element. The diagrams likely serve as a visual aid for understanding and manipulating these graph structures.
</details>
With the exception of the , all other elementary graphs have three edges. The graph has only one edge.
There are two types of 'fork' graphs, the λ graph and the Υ graph, and two types of 'join' graphs, the graph and the ¯ ε graph. Further I briefly explain what are they supposed to represent and why they are needed in this graphic formalism.
The λ gate corresponds to the lambda abstraction operation from untyped lambda calculus. This gate has one input (the entry arrow) and two outputs (the exit arrows), therefore, at first view, it cannot be a graphical representation of an operation. In untyped lambda calculus the λ abstraction operation has two inputs, namely a variable name x and a term A , and one output, the term λx.A . There is an algorithm, presented in section 3, which
transforms a lambda calculus term into a graph made by elementary gates, such that to any lambda abstraction which appears in the term corresponds a λ gate.
The Υ gate corresponds to a FAN-OUT gate. It is needed because the graphic lambda calculus described in this article does not have variable names. Υgates appear in the process of elimination of variable names from lambda terms, in the algorithm previously mentioned.
Another justification for the existence of two fork graphs is that they are subjected to different moves: the λ gate appears in the graphic beta move, together with the gate, while the Υ gate appears in the FAN-OUT moves. Thus, the λ and Υ gates, even if they have the same topology, they are subjected to different moves, which in fact characterize their 'lambda abstraction'-ness and the 'fan-out'-ness of the respective gates. The alternative, which consists into using only one, generic, fork gate, leads to the identification, in a sense, of lambda abstraction with fan-out, which would be confusing.
The gate corresponds to the application operation from lambda calculus. The algorithm from section 3 associates a gate to any application operation used in a lambda calculus term.
The ¯ ε gate corresponds to an idempotent right quasigroup operation, which appears in emergent algebras, as an abstractization of the geometrical operation of taking a dilation (of coefficient ε ), based at a point and applied to another point.
As previously, the existence of two join gates, with the same topology, is justified by the fact that they appear in different moves.
1. The set GRAPH. We construct the set of graphs GRAPH over the graphical alphabet by grafting edges of a finite number of copies of the elements of the graphical alphabet.
Definition 2.2 GRAPH is the set of graphs obtained by grafting edges of a finite number of copies of the elements of the graphical alphabet. During the grafting procedure, we start from a set of gates and we add, one by one, a finite number of gates, such that, at any step, any edge of any elementary graph is grafted on any other free edge (i.e. not already grafted to other edge) of the graph, with the condition that they have the same orientation.
For any node of the graph, the local embedding into the plane is given by the element of the graphical alphabet which decorates it.
The set of free edges of a graph G ∈ GRAPH is named the set of leaves L ( G ) . Technically, one may imagine that we complete the graph G ∈ GRAPH by adding to the free extremity of any free edge a decorated node, called 'leaf', with decoration 'IN' or 'OUT', depending on the orientation of the respective free edge. The set of leaves L ( G ) thus decomposes into a disjoint union L ( G ) = IN ( G ) ∪ OUT ( G ) of in or out leaves.
Moreover, we admit into GRAPH arrows without nodes, , called wires or lines, and loops (without nodes from the elementary graphs, nor leaves)
<details>
<summary>Image 2 Details</summary>
### Visual Description
## Diagram: Circular Flow
### Overview
The image depicts a simple diagram of a circular flow. It consists of an oval shape with an arrow indicating the direction of the flow.
### Components/Axes
* **Shape:** An oval shape representing the flow path.
* **Arrow:** A small arrow indicating the direction of the flow, located on the right side of the oval.
### Detailed Analysis
The diagram shows a closed-loop system. The arrow indicates a clockwise direction of flow. The oval shape is not a perfect circle, but rather an elongated oval.
### Key Observations
The diagram is very simple and lacks any specific labels or values. It represents a general concept of circular flow.
### Interpretation
The diagram illustrates a basic concept of a cyclical process or system where elements continuously circulate. Without additional context, it's difficult to determine the specific application or meaning of this circular flow. It could represent a feedback loop, a cycle of events, or a closed system.
</details>
Graphs in GRAPH can be disconnected. Any graph which is a finite reunion of lines, loops and assemblies of the elementary graphs is in GRAPH .
2. Local moves. These are transformations of graphs in GRAPH which are local, in the sense that any of the moves apply to a limited part of a graph, keeping the rest of the graph unchanged.
We may define a local move as a rule of transformation of a graph into another of the following form.
First, a subgraph of a graph G in GRAPH is any collection of nodes and/or edges of G . It is not supposed that the mentioned subgraph must be in GRAPH . Also, a collection
of some edges of G , without any node, count as a subgraph of G . Thus, a subgraph of G might be imagined as a subset of the reunion of nodes and edges of G .
For any natural number N and any graph G in GRAPH , let P ( G,N ) be the collection of subgraphs P of the graph G which have the sum of the number of edges and nodes less than or equal to N .
Definition 2.3 A local move has the following form: there is a number N and a condition C which is formulated in terms of graphs which have the sum of the number of edges and nodes less than or equal to N , such that for any graph G in GRAPH and for any P ∈ P ( G,N ) , if C is true for P then transform P into P ′ , where P ′ is also a graph which have the sum of the number of edges and nodes less than or equal to N .
Graphically we may group the elements of the subgraph, subjected to the application of the local rule, into a region encircled with a dashed closed, simple curve. The edges which cross the curve (thus connecting the subgraph P with the rest of the graph) will be numbered clockwise. The transformation will affect only the part of the graph which is inside the dashed curve (inside meaning the bounded connected part of the plane which is bounded by the dashed curve) and, after the transformation is performed, the edges of the transformed graph will connect to the graph outside the dashed curve by respecting the numbering of the edges which cross the dashed line.
However, the grouping of the elements of the subgraph has no intrinsic meaning in graphic lambda calculus. It is just a visual help and it is not a part of the formalism. As a visual help, I shall use sometimes colors in the figures. The colors, as well, don't have any intrinsic meaning in the graphic lambda calculus.
2.1. Graphic β move. This is the most important move, inspired by the β -reduction from lambda calculus, see theorem 3.1, part (d).
<details>
<summary>Image 3 Details</summary>
### Visual Description
## Diagram: Feynman Diagram Transformation
### Overview
The image presents a diagram illustrating a transformation between two Feynman diagrams. The left diagram shows particles 1 and 4 interacting via intermediate particles represented by circles containing symbols lambda and lambda-bar, resulting in particles 2 and 3. The right diagram shows particles 1 and 4 directly becoming particles 3 and 2. The transformation between these two diagrams is indicated by a blue curved arrow labeled with the Greek letter beta.
### Components/Axes
* **Particles:** Labeled 1, 2, 3, and 4.
* **Interaction Vertices:** Two circular vertices, one containing "λ" (lambda) and the other containing "λ̄" (lambda-bar).
* **Arrows:** Indicate the direction of particle flow.
* **Transformation Arrow:** A blue curved arrow labeled "β" (beta) indicating the transformation between the two diagrams.
### Detailed Analysis
**Left Diagram:**
* Particle 1 enters from the left and interacts at the top vertex (λ).
* Particle 4 enters from the left and interacts at the bottom vertex (λ̄).
* An internal line connects the two vertices, with an arrow pointing downwards.
* Particle 2 exits from the right of the top vertex.
* Particle 3 exits from the right of the bottom vertex.
**Right Diagram:**
* Particle 1 enters from the left and becomes particle 3 on the right.
* Particle 4 enters from the left and becomes particle 2 on the right.
**Transformation:**
* A blue curved arrow labeled "β" connects the two diagrams, indicating a transformation or equivalence between them. The arrow is bidirectional, suggesting the transformation can occur in either direction.
### Key Observations
* The diagram illustrates a relationship between two different representations of a particle interaction.
* The blue arrow labeled beta indicates a transformation between the two diagrams.
* The left diagram shows an interaction mediated by intermediate particles, while the right diagram shows a direct interaction.
### Interpretation
The diagram likely represents a mathematical or physical equivalence between two different ways of calculating the same process in quantum field theory. The left diagram represents a higher-order process involving intermediate particles, while the right diagram represents a lower-order, direct interaction. The transformation indicated by "β" suggests that the higher-order process can be approximated or related to the lower-order process under certain conditions. This could be related to concepts like effective field theories or renormalization group flows, where complex interactions are simplified to their essential components at a particular energy scale.
</details>
The labels '1, 2, 3, 4' are used only as guides for gluing correctly the new pattern, after removing the old one. As with the encircling dashed curve, they have no intrinsic meaning in graphic lambda calculus.
This 'sewing braids' move will be used also in contexts outside of lambda calculus! It is the most powerful move in this graphic calculus. A primitive form of this move appears as the re-wiring move (W1) (section 3.3, p. 20 and the last paragraph and figure from section 3.4, p. 21 in [6]).
An alternative notation for this move is the following:
<details>
<summary>Image 4 Details</summary>
### Visual Description
## Diagram: Feynman Diagram Transformation
### Overview
The image depicts a transformation between two Feynman diagrams, connected by a blue double-headed arrow labeled "β". The diagram on the left represents an interaction mediated by two vertices, each labeled with "λ". The diagram on the right represents a direct interaction.
### Components/Axes
* **Diagram 1 (Left):**
* External lines labeled 1, 2, 3, and 4.
* Arrows on lines indicate direction. Lines 1 and 4 are incoming, lines 2 and 3 are outgoing.
* Two vertices, each enclosed in a circle. The top vertex contains the symbol "λ", and the bottom vertex contains the symbol "Λ".
* An internal line connects the two vertices, with an arrow indicating direction from the top vertex to the bottom vertex.
* **Diagram 2 (Right):**
* External lines labeled 1, 2, 3, and 4.
* Arrows on lines indicate direction. Lines 1 and 4 are incoming, lines 2 and 3 are outgoing.
* A single vertex where all four lines intersect.
* **Transformation Arrow:**
* A blue double-headed arrow connects the two diagrams, indicating a transformation or equivalence.
* The arrow is labeled "β" above it.
### Detailed Analysis or ### Content Details
* **Diagram 1:**
* Line 1 enters from the left and connects to the top vertex.
* Line 2 exits to the right from the top vertex.
* Line 4 enters from the left and connects to the bottom vertex.
* Line 3 exits to the right from the bottom vertex.
* The internal line connects the top vertex to the bottom vertex.
* **Diagram 2:**
* Line 1 enters from the top-left and connects to the central vertex.
* Line 2 exits to the top-right from the central vertex.
* Line 4 enters from the bottom-left and connects to the central vertex.
* Line 3 exits to the bottom-right from the central vertex.
* Lines 1 and 3 cross over each other.
* Lines 2 and 4 cross over each other.
### Key Observations
* The transformation relates a two-vertex interaction to a single-vertex interaction.
* The parameter "β" likely represents a coupling constant or a transformation parameter.
* The symbols "λ" and "Λ" at the vertices in the first diagram likely represent coupling strengths.
### Interpretation
The image illustrates a possible transformation between two different representations of a physical process. The diagram on the left represents a process mediated by an intermediate state, while the diagram on the right represents a direct interaction. The parameter "β" likely governs the strength or probability of this transformation. This type of transformation is common in quantum field theory, where different diagrams can represent the same physical process at different levels of approximation. The presence of "λ" and "Λ" suggests that the strength of the interaction at each vertex is important for understanding the overall process.
</details>
A move which looks very much alike the graphic beta move is the UNZIP operation from the formalism of knotted trivalent graphs, see for example the paper [21] section 3. In order to see this, let's draw again the graphic beta move, this time without labeling the arrows:
<details>
<summary>Image 5 Details</summary>
### Visual Description
## Diagram: Feynman Diagram Transformation
### Overview
The image depicts a transformation between two Feynman diagrams, connected by a blue, double-headed arrow labeled with the Greek letter beta (β). The diagram on the left shows two vertices connected by an internal line, each vertex having two external lines. The diagram on the right shows two crossing lines.
### Components/Axes
* **Left Diagram:**
* Two vertices, each represented by a circle.
* The left vertex is labeled with "λ" (lambda).
* The right vertex is labeled with "Λ" (Lambda).
* Each vertex has two incoming/outgoing lines.
* The vertices are connected by a single internal line with an arrow indicating direction.
* **Transformation Arrow:**
* A blue, double-headed curved arrow connects the two diagrams.
* The arrow is labeled with "β" (beta) above it.
* **Right Diagram:**
* Two lines crossing each other.
* Each line has an arrow indicating direction.
### Detailed Analysis
* **Left Diagram:** The left vertex has two incoming lines and one outgoing line. The right vertex has one incoming line and two outgoing lines. The internal line connects the two vertices, with the arrow pointing from the left vertex (λ) to the right vertex (Λ).
* **Transformation Arrow:** The blue arrow indicates a transformation or relationship between the two diagrams. The "β" likely represents a parameter or process associated with this transformation.
* **Right Diagram:** The two lines cross each other. One line has an arrow pointing from the bottom-left to the top-right. The other line has an arrow pointing from the top-left to the bottom-right.
### Key Observations
* The diagram shows a transformation between a vertex-based interaction (left) and a direct interaction (right).
* The "β" parameter likely governs the strength or probability of this transformation.
* The arrows on the lines indicate the direction of particle flow.
### Interpretation
The image represents a relationship between two different ways of representing a physical process in quantum field theory. The left diagram shows an interaction mediated by vertices and internal lines, while the right diagram shows a direct interaction. The transformation between these two representations is governed by the parameter "β". This could represent a change of basis or a different way of calculating the same physical quantity. The specific meaning of "λ", "Λ", and "β" would depend on the context of the physical system being described.
</details>
The unzip operation acts only from left to right in the following figure. Remarkably, it acts on trivalent graphs (but not oriented).
<details>
<summary>Image 6 Details</summary>
### Visual Description
## Diagram: Unzip Transformation
### Overview
The image depicts a diagram illustrating a transformation labeled "UNZIP". A connected graph on the left is transformed into two parallel lines on the right. The transformation is indicated by a blue curved arrow.
### Components/Axes
* **Left Side:** A graph consisting of two nodes (represented by black dots) connected by a single edge (a black line). Each node also has two additional edges extending outwards.
* **Transformation Arrow:** A blue curved arrow pointing from the left graph to the right side, labeled "UNZIP" in blue text above the arrow.
* **Right Side:** Two parallel, horizontal black lines.
### Detailed Analysis or ### Content Details
1. **Left Graph:**
* Two nodes connected by a single edge.
* Each node has two additional edges extending outwards at approximately 45-degree angles from the connecting edge.
2. **UNZIP Transformation:**
* The blue arrow indicates the transformation process.
* The text "UNZIP" describes the type of transformation.
3. **Right Side:**
* Two parallel lines of equal length.
* The lines are horizontally aligned.
### Key Observations
* The "UNZIP" transformation separates the connected graph into two distinct lines.
* The nodes in the original graph seem to correspond to the endpoints of the resulting lines.
### Interpretation
The diagram illustrates a conceptual transformation where a connected graph structure is "unzipped" or separated into two parallel lines. This could represent a simplification or decomposition of a more complex structure into its constituent parts. The "UNZIP" label suggests a process of unraveling or separating interconnected elements.
</details>
Let us go back to the graphic beta move and remark that it does not depend on the particular embedding in the plane. For example, the intersection of the '1,3' arrow with the '4,2' arrow is an artifact of the embedding, there is no node there. Intersections of arrows have no meaning, remember that we work with graphs which are locally planar, not globally planar.
The graphic beta move goes into both directions. In order to apply the move, we may pick a pair of arrows and label them with '1,2,3,4', such that, according to the orientation of the arrows, '1' points to '3' and '4' points to '2', without any node or label between '1' and '3' and between '4' and '2' respectively. Then, by a graphic beta move, we may replace the portions of the two arrows which are between '1' and '3', respectively between '4' and '2', by the pattern from the LHS of the figure.
The graphic beta move may be applied even to a single arrow, or to a loop. In the next figure we see three applications of the graphic beta move. They illustrate the need for considering loops and wires as members of GRAPH .
<details>
<summary>Image 7 Details</summary>
### Visual Description
## Diagram: Beta Reduction Examples
### Overview
The image illustrates examples of beta reduction in a diagrammatic notation. It shows three separate cases, each demonstrating a transformation from one diagrammatic representation to another, connected by a "beta" reduction step.
### Components/Axes
* **Diagrams:** Each case consists of two diagrams. The left-hand side diagram is transformed into the right-hand side diagram.
* **Arrows:** Arrows represent connections or flow. They can be straight lines or curved loops.
* **Nodes:** Nodes are represented by circles. Some nodes contain the symbol "λ" inside. Other nodes contain a symbol resembling an upside-down lambda.
* **Labels:** Red numbers (1, 2, 3, 4) label the connections or endpoints of the diagrams.
* **Beta Reduction Indicator:** A blue curved arrow labeled "β" indicates the beta reduction step between the diagrams.
### Detailed Analysis
**Case 1 (Top Row):**
* **Left Diagram:** A straight arrow with labels 1, 3, 4, and 2. The arrow points from 1 to 2. The labels are ordered as 1-3-4-2 along the line.
* **Beta Reduction:** Indicated by the blue "β" arrow.
* **Right Diagram:** A node containing "λ" with incoming arrow labeled 1 and outgoing arrow labeled 2. A node containing an upside-down lambda is connected to the "λ" node by a downward arrow. This second node has an outgoing loop labeled 4 and an outgoing arrow labeled 3.
**Case 2 (Middle Row):**
* **Left Diagram:** A straight arrow with labels 4, 2, 1, and 3. The arrow points from 4 to 3. The labels are ordered as 4-2-1-3 along the line.
* **Beta Reduction:** Indicated by the blue "β" arrow.
* **Right Diagram:** A node containing "λ" with a loop labeled 1 and 2. A node containing an upside-down lambda is connected to the "λ" node by a downward arrow. This second node has incoming arrow labeled 4 and outgoing arrow labeled 3.
**Case 3 (Bottom Row):**
* **Left Diagram:** A closed loop with labels 1, 2, 4, and 3. The loop proceeds from 1 to 2 to 4 to 3 and back to 1.
* **Beta Reduction:** Indicated by the blue "β" arrow.
* **Right Diagram:** A node containing "λ" with a loop labeled 1 and 2. A node containing an upside-down lambda is connected to the "λ" node by a downward arrow. This second node has an outgoing loop labeled 4 and an outgoing arrow labeled 3.
### Key Observations
* Each case demonstrates a transformation of a diagram involving arrows and labels into a diagram involving nodes with "λ" and upside-down lambda symbols.
* The "β" arrow consistently indicates a beta reduction step.
* The red numbers appear to represent indices or labels associated with the connections in the diagrams.
### Interpretation
The diagrams illustrate beta reduction, a fundamental concept in lambda calculus and functional programming. The "β" arrow represents the application of a beta reduction rule, which involves substituting a value for a variable within a lambda expression. The diagrams provide a visual representation of this substitution process, showing how the connections and labels are rearranged during the reduction. The "λ" symbol represents a lambda abstraction, while the upside-down lambda symbol likely represents an application or a bound variable. The specific meaning of the diagrams would depend on the precise notation being used, but the overall concept is the transformation of a lambda expression through substitution.
</details>
Also, we can apply in different ways a graphic beta move, to the same graph and in the
same place, simply by using different labels '1', ... '4' (here A , B , C , D are graphs in GRAPH ):
A particular case of the previous figure is yet another justification for having loops as elements in GRAPH .
<details>
<summary>Image 8 Details</summary>
### Visual Description
## Diagram: Beta Reduction
### Overview
The image depicts two diagrams illustrating beta reduction steps in a computational process. Each diagram shows a transformation from a complex structure on the left to a simplified structure on the right, connected by a blue double-headed arrow labeled "β". The diagrams involve nodes labeled A, B, C, and D, along with lambda (λ) and application (Y) symbols, and directed edges numbered 1, 2, 3, and 4.
### Components/Axes
* **Nodes:** Represented by irregular shapes, labeled A, B, C, and D.
* **Lambda Abstraction (λ):** Represented by a circle containing the lambda symbol.
* **Application (Y):** Represented by a circle containing the application symbol.
* **Edges:** Represented by arrows, labeled with numbers 1, 2, 3, and 4 in red.
* **Beta Reduction (β):** Represented by a blue double-headed arrow labeled "β".
### Detailed Analysis
**Top Diagram:**
* **Left Side:**
* Node A has an outgoing edge (1) to a lambda abstraction (λ).
* Node D has an outgoing edge (4) to an application (Y).
* The lambda abstraction (λ) has an outgoing edge (2) to node C.
* The application (Y) has an outgoing edge (3) to node B.
* The lambda abstraction (λ) and application (Y) are connected by a vertical edge.
* **Right Side:**
* Node A has an outgoing edge (1) to node B, labeled with number 3.
* Node D has an outgoing edge (4) to node C, labeled with number 2.
**Bottom Diagram:**
* **Left Side:**
* Node D has an outgoing edge (1) to a lambda abstraction (λ).
* Node A has an outgoing edge (4) to an application (Y).
* The lambda abstraction (λ) has an outgoing edge (2) to node B.
* The application (Y) has an outgoing edge (3) to node C.
* The lambda abstraction (λ) and application (Y) are connected by a vertical edge.
* **Right Side:**
* Node A has an outgoing edge (4) to node B, labeled with number 2.
* Node D has an outgoing edge (1) to node C, labeled with number 3.
### Key Observations
* The diagrams illustrate a transformation process, likely a form of beta reduction in lambda calculus or a related computational model.
* The "β" symbol indicates the application of a beta reduction rule.
* The numbered edges likely represent the order or dependencies in the reduction process.
* The lambda abstraction and application symbols suggest function application and abstraction operations.
### Interpretation
The diagrams demonstrate how a complex expression involving lambda abstractions and applications can be simplified through beta reduction. The transformation involves rearranging the connections between nodes A, B, C, and D, effectively substituting the argument into the function body. The numbered edges likely represent the flow of data or the order of operations during the reduction. The two diagrams show different initial configurations and their corresponding reduced forms, highlighting the versatility of the beta reduction process.
</details>
These two applications of the graphic beta move may be represented alternatively like this:
<details>
<summary>Image 9 Details</summary>
### Visual Description
## Diagram: Beta Reduction
### Overview
The image depicts two diagrams illustrating beta reduction in lambda calculus. Each diagram shows a transformation step, with the left side representing the initial expression and the right side representing the reduced expression. The transformations are labeled with "β" and involve the manipulation of lambda abstractions and applications.
### Components/Axes
* **Nodes:** The diagrams contain nodes labeled "C" and "D", which appear to represent terms or expressions. These nodes have a star-like shape.
* **Lambda Abstraction:** A node labeled "λ" represents a lambda abstraction.
* **Application:** A node with the symbol "∀" represents an application.
* **Arrows:** Arrows indicate the flow of data or the application of functions. The arrows are numbered 1, 2, 3, and 4 in red.
* **Beta Reduction Label:** The symbol "β" with a double-headed arrow indicates the beta reduction step.
### Detailed Analysis
**Top Diagram:**
* **Left Side:**
* Node "D" on the left.
* Arrow labeled "1" goes from "D" to the lambda abstraction node "λ".
* Arrow labeled "2" goes from "λ" to node "C" on the right.
* Node "∀" is below "λ".
* Arrow labeled "4" goes from "D" to "∀".
* Arrow labeled "3" goes from "∀" to "C".
* A curved line connects "C" to "D", forming a loop.
* **Right Side:**
* An oval with an arrow labeled "1" going to the right and "3" going to the left.
* Node "D" on the left.
* Arrow labeled "4" goes from "D" to node "C" on the right.
* Node "C" on the right.
**Bottom Diagram:**
* **Left Side:**
* Node "D" on the left.
* Arrow labeled "1" goes from "D" to the lambda abstraction node "λ".
* Arrow labeled "2" goes from "λ" to node "C" on the right.
* Node "∀" is below "λ".
* Arrow labeled "4" goes from "D" to "∀".
* Arrow labeled "3" goes from "∀" to "C".
* A curved line connects "D" to "C", forming a loop.
* **Right Side:**
* An oval with an arrow labeled "4" going to the right and "2" going to the left.
* Node "D" on the left.
* Arrow labeled "1" goes from "D" to node "C" on the right.
* Node "C" on the right.
### Key Observations
* The diagrams illustrate the transformation of a lambda expression involving application and abstraction into a simpler form through beta reduction.
* The "β" symbol indicates the application of the beta reduction rule.
* The arrows represent the flow of data or the application of functions.
* The nodes "C" and "D" represent terms or expressions.
### Interpretation
The diagrams demonstrate the process of beta reduction, a fundamental operation in lambda calculus. Beta reduction involves substituting the argument of a lambda abstraction into its body. The diagrams show how a complex expression involving lambda abstraction and application can be simplified through this process. The specific details of the lambda expressions are not explicitly given, but the diagrams illustrate the general transformation that occurs during beta reduction. The diagrams show two different beta reductions, each transforming a more complex expression on the left into a simpler expression on the right. The curved lines on the left side of each diagram suggest a binding or dependency between the terms.
</details>
<details>
<summary>Image 10 Details</summary>
### Visual Description
## Diagram: Lambda Calculus Beta Reduction
### Overview
The image depicts two examples of beta reduction in lambda calculus, shown as transformations between two states. Each example consists of a diagram on the left side, a blue double-headed arrow labeled "β" in the center, and a transformed diagram on the right side. The diagrams involve nodes labeled "D" and "C", lambda abstractions (λ), and directed edges labeled with numbers 1, 2, 3, and 4.
### Components/Axes
* **Nodes:**
* "D": Represents a data term.
* "C": Represents a computation term.
* "λ": Represents a lambda abstraction.
* **Edges:** Directed edges represent function application or data flow. They are labeled with numbers 1, 2, 3, and 4, indicating the order or association of the terms.
* **Transformation Arrow:** A blue double-headed arrow labeled "β" indicates the beta reduction step.
* **Labels:** The labels "D", "C", "λ", "β", and the numbers 1-4 are in black or blue (for β) and red respectively.
### Detailed Analysis
**Top Example:**
* **Left Side:**
* Node "D" has an outgoing edge labeled "4" pointing to a node with a small downward-pointing triangle.
* The triangle node has outgoing edge labeled "1" and incoming edge labeled "3" both connecting to a lambda abstraction node "λ".
* The lambda abstraction node "λ" has an outgoing edge labeled "2" pointing to node "C".
* The lambda abstraction node "λ" also has an outgoing edge labeled "1" that loops back to itself.
* The triangle node also has an outgoing edge labeled "3" that loops back to itself.
* **Transformation:** Beta reduction (β).
* **Right Side:**
* A loop with an arrow and labels "1" and "3".
* Node "D" has an outgoing edge labeled "4" pointing to node "C", which has an outgoing edge labeled "2".
**Bottom Example:**
* **Left Side:**
* Node "D" has an outgoing edge labeled "1" pointing to a lambda abstraction node "λ".
* The lambda abstraction node "λ" has an outgoing edge labeled "2" that loops back to itself.
* The lambda abstraction node "λ" has an outgoing edge that crosses over to a node with a small downward-pointing triangle, which has an outgoing edge labeled "3" pointing to node "C".
* The triangle node has an outgoing edge labeled "4" that loops back to itself.
* **Transformation:** Beta reduction (β).
* **Right Side:**
* A loop with an arrow and labels "4" and "2".
* Node "D" has an outgoing edge labeled "1" pointing to node "C", which has an outgoing edge labeled "3".
### Key Observations
* The diagrams illustrate how beta reduction simplifies lambda expressions by substituting the argument of a function into its body.
* The numbered edges indicate the flow of data or the association of terms during the reduction process.
* The lambda abstraction nodes "λ" disappear after the beta reduction, and the connections are rearranged.
* The loops on the right side of the top example are labeled "1" and "3", while the loops on the right side of the bottom example are labeled "4" and "2".
### Interpretation
The image provides a visual representation of beta reduction, a fundamental operation in lambda calculus. It demonstrates how complex expressions involving lambda abstractions can be simplified into equivalent, more direct forms. The numbered edges help track the flow of data and the relationships between terms during the reduction process. The two examples show different configurations of lambda expressions and their corresponding reduced forms, highlighting the versatility of beta reduction in simplifying various lambda calculus expressions. The loops that appear after the beta reduction represent self-application or recursion.
</details>
- 2.2. (CO-ASSOC) move. This is the 'co-associativity' move involving the Υ graphs. We think about the Υ graph as corresponding to a FAN-OUT gate.
<details>
<summary>Image 11 Details</summary>
### Visual Description
## Diagram: Co-Associativity Diagram
### Overview
The image presents a diagram illustrating the concept of co-associativity. It consists of two tree-like structures connected by a curved arrow labeled "CO-ASSOC". Each tree structure has a root node labeled "1", two intermediate nodes, and two leaf nodes labeled "2", "3", and "4". Arrows indicate the flow or direction within the structure.
### Components/Axes
* **Nodes:** Each tree structure contains nodes represented by circles with a "Y" shape inside. These nodes act as branching or merging points.
* **Edges:** Lines connect the nodes, representing relationships or flow. Each line has an arrow indicating direction.
* **Labels:** The numbers 1, 2, 3, and 4 label the nodes.
* **Arrow:** A curved blue arrow connects the two tree structures, indicating a transformation or equivalence.
* **Text:** The text "CO-ASSOC" is positioned below the arrow, describing the transformation.
### Detailed Analysis
**Left Tree Structure:**
* A line originates from node "1" at the bottom and points upwards to a node.
* From this node, two lines branch out. One goes to the top-left, ending at node "2". The other goes to the top-right, leading to another node.
* From the second node, two lines branch out again. One goes to the top, ending at node "3". The other goes to the right, ending at node "4".
**Right Tree Structure:**
* The right tree structure is a mirror image of the left tree structure.
* A line originates from node "1" at the bottom and points upwards to a node.
* From this node, two lines branch out. One goes to the top-right, ending at node "4". The other goes to the top-left, leading to another node.
* From the second node, two lines branch out again. One goes to the top, ending at node "3". The other goes to the left, ending at node "2".
**Arrow and Label:**
* A blue curved arrow points from the right tree structure to the left tree structure.
* The text "CO-ASSOC" is positioned below the arrow.
### Key Observations
* The diagram illustrates a transformation between two equivalent tree structures.
* The nodes labeled "2", "3", and "4" are rearranged between the two structures.
* The arrow indicates a direction of transformation or equivalence.
### Interpretation
The diagram represents the concept of co-associativity, likely in the context of category theory or abstract algebra. The two tree structures represent different ways of composing or combining operations, and the "CO-ASSOC" arrow indicates that these two compositions are equivalent. The specific meaning depends on the context in which this diagram is used, but it generally implies that the order in which certain operations are performed does not affect the final result, up to a certain equivalence.
</details>
By using CO-ASSOC moves, we can move between any two binary trees formed only with Υ gates, with the same number of output leaves.
- 2.3. (CO-COMM) move. This is the 'co-commutativity' move involving the Υ gate. It will be not used until the section 6 concerning knot diagrams.
- 2.3.a (R1a) move. This move is imported from emergent algebras. Explanations are given in section 5. It involves an Υ graph and a ¯ ε graph, with ε ∈ Γ.
<details>
<summary>Image 12 Details</summary>
### Visual Description
## Diagram: Co-Commutativity Diagrams
### Overview
The image presents two diagrams illustrating the concept of co-commutativity. The diagrams depict relationships between inputs and outputs, represented by lines and arrows, connected through a central node. A blue arrow labeled "CO-COMM" indicates the transformation or relationship between the two diagrams.
### Components/Axes
* **Nodes:** Each diagram contains a central circular node with a "Y" shape inside.
* **Inputs/Outputs:** Each diagram has three lines, labeled 1, 2, and 3, representing inputs or outputs. Arrows on the lines indicate the direction of flow.
* **Arrows:** Arrows on the lines indicate the direction of flow.
* **Co-Comm Arrow:** A blue, curved, double-headed arrow labeled "CO-COMM" connects the two diagrams, indicating a transformation or relationship between them.
### Detailed Analysis
**Left Diagram:**
* Line 1: Enters the node from the bottom, with an arrow pointing upwards.
* Line 2: Starts at the top-left, crosses over Line 3, and forms a loop that enters the node. The arrow points towards the node.
* Line 3: Starts at the top-right, crosses over Line 2, and forms a loop that enters the node. The arrow points towards the node.
**Right Diagram:**
* Line 1: Enters the node from the bottom, with an arrow pointing upwards.
* Line 2: Enters the node from the top-left, with an arrow pointing downwards.
* Line 3: Enters the node from the top-right, with an arrow pointing downwards.
**Co-Comm Arrow:**
* The blue "CO-COMM" arrow points from the left diagram to the right diagram, indicating a transformation or relationship.
### Key Observations
* The left diagram shows a more complex interaction with lines 2 and 3 crossing and looping before entering the node.
* The right diagram shows a simpler interaction with lines 2 and 3 directly entering the node.
* The "CO-COMM" arrow suggests that the left diagram can be transformed into the right diagram, representing a co-commutativity relationship.
### Interpretation
The diagrams illustrate the concept of co-commutativity, likely in the context of algebra or category theory. The left diagram represents a more complex operation or structure, while the right diagram represents a simplified or equivalent form. The "CO-COMM" arrow indicates that the two diagrams are related by a co-commutativity property, meaning that the order of operations or inputs does not affect the final result. The diagrams are a visual representation of an algebraic or categorical relationship, demonstrating how a complex structure can be simplified or transformed while preserving its essential properties.
</details>
<details>
<summary>Image 13 Details</summary>
### Visual Description
## Diagram: Reidemeister Move R1a
### Overview
The image depicts a diagram illustrating the Reidemeister move of type 1a (R1a). It shows a transformation of a knot diagram where a loop is added to or removed from a strand.
### Components/Axes
* **Left Side:** A strand with two circular nodes labeled "ε" (epsilon) and "Y" (gamma). The strand has arrows indicating direction. A loop connects the two nodes.
* **Center:** A blue curved arrow labeled "R1a" indicating the transformation. The arrow points from left to right.
* **Right Side:** A single strand with an arrow indicating direction.
### Detailed Analysis
* **Left Side:**
* The strand enters from the bottom-left, passes through a node labeled "Y", then forms a loop connecting back to a node labeled "ε", and continues upward.
* The loop consists of two curved lines, each with an arrow indicating direction. The arrows on the loop point in opposite directions.
* The main strand has arrows pointing upwards.
* **Center:**
* The blue curved arrow labeled "R1a" indicates the transformation from the left side to the right side.
* **Right Side:**
* A single strand enters from the bottom-right and continues upwards.
* The strand has an arrow pointing upwards.
### Key Observations
* The diagram illustrates the Reidemeister move R1a, which involves adding or removing a loop from a strand.
* The left side shows a strand with a loop, while the right side shows the same strand without the loop.
* The blue arrow labeled "R1a" indicates the transformation.
### Interpretation
The diagram demonstrates the Reidemeister move R1a, a fundamental concept in knot theory. This move shows that a knot diagram with a loop can be simplified to a diagram without the loop, and vice versa, without changing the underlying knot. The labels "ε" and "Y" on the nodes are likely related to the specific type of crossing or twist in the knot diagram. The diagram illustrates the equivalence between the two knot diagrams, highlighting the invariance of knots under Reidemeister moves.
</details>
2.3.b (R1b) move. The move R1b (also related to emergent algebras) is this:
<details>
<summary>Image 14 Details</summary>
### Visual Description
## Diagram: Reidemeister Move R1b
### Overview
The image depicts a Reidemeister move of type 1b (R1b). It shows a transformation of a line with a curl into a straight line. The transformation is indicated by a curved, double-headed arrow labeled "R1b".
### Components/Axes
* **Lines:** Represent strands or strings in a knot diagram.
* **Arrows:** Indicate the orientation or direction of the strands.
* **Curl:** A loop or twist in the strand. One side of the curl is labeled with "ε" inside a circle, and the other side is labeled with "Y" inside a circle.
* **Transformation Arrow:** A curved, double-headed arrow indicating the transformation from the left side to the right side of the diagram.
* **Label:** "R1b" above the transformation arrow.
### Detailed Analysis
The diagram shows a transformation from a line with a curl to a straight line.
* **Left Side:** A line segment with an arrow indicating its direction. The line has a curl in it. The curl consists of two loops. One loop is labeled with "ε" inside a circle, and the other loop is labeled with "Y" inside a circle. The arrows on the line indicate the direction of the strand.
* **Transformation:** A curved, double-headed arrow points from the left side to the right side, indicating the transformation. The arrow is labeled "R1b".
* **Right Side:** A straight line segment with an arrow indicating its direction.
### Key Observations
* The curl on the left side is removed in the transformation, resulting in a straight line on the right side.
* The direction of the line is maintained throughout the transformation.
* The label "R1b" identifies the type of Reidemeister move.
### Interpretation
The diagram illustrates the Reidemeister move R1b, which is a fundamental operation in knot theory. This move allows for the simplification of knot diagrams by removing a curl in a strand. The transformation maintains the knot's overall structure while reducing its complexity. The labels "ε" and "Y" on the curl likely represent specific properties or orientations of the curl that are relevant in the context of the knot theory being presented.
</details>
2.4. (R2) move. This corresponds to the Reidemeister II move for emergent algebras. It involves an Υ graph and two other: a ¯ ε and a ¯ µ graph, with ε, µ ∈ Γ.
<details>
<summary>Image 15 Details</summary>
### Visual Description
## Diagram: R2 Transformation
### Overview
The image depicts a diagram illustrating a transformation, labeled "R2," between two configurations of interconnected elements. The diagram uses arrows to indicate directionality and circles to represent nodes labeled with Greek letters. The transformation shows how a more complex arrangement on the left can be simplified to a more compact form on the right.
### Components/Axes
* **Nodes:** Represented by circles, labeled with Greek letters: μ, ε, and γ.
* **Arrows:** Indicate directionality or flow between nodes.
* **Labels:** Numerical labels (1, 2, 3) in red, positioned near the ends of arrows.
* **Transformation Label:** "R2" with a double-headed curved arrow indicating the transformation direction.
### Detailed Analysis
**Left Configuration:**
* A node labeled "γ" is located at the bottom-left. An arrow labeled "1" in red originates from this node.
* A node labeled "ε" is positioned below and to the right of the "γ" node. An arrow labeled "2" in red originates from this node.
* A node labeled "μ" is positioned above and to the right of the "γ" node.
* An arrow labeled "3" in red originates from the "μ" node.
* Arrows connect the nodes in the following manner:
* "γ" to "μ"
* "γ" to "ε"
* "ε" to "μ"
**Transformation:**
* A blue, double-headed curved arrow labeled "R2" indicates the transformation from the left configuration to the right configuration.
**Right Configuration:**
* A single node labeled "εμ" is present.
* An arrow labeled "1" in red originates from this node.
* An arrow labeled "2" in red originates from this node.
* An arrow labeled "3" in red originates from this node.
### Key Observations
* The transformation "R2" simplifies the interconnected network of three nodes (γ, ε, μ) into a single node (εμ).
* The arrows labeled 1, 2, and 3 are preserved during the transformation, indicating a conservation of flow or directionality.
### Interpretation
The diagram illustrates a simplification process, possibly in a mathematical or physical context. The "R2" transformation suggests a rule or operation that allows for the reduction of a complex system into a simpler, equivalent representation. The preservation of the arrows labeled 1, 2, and 3 implies that certain properties or quantities associated with these arrows are conserved during the transformation. The diagram could represent a simplification of a network, a reduction of a complex equation, or a transformation in a physical system.
</details>
This move appears in section 3.4, p. 21 [6], with the supplementary name 'triangle move'.
- 2.5. (ext2) move. This corresponds to the rule (ext2) from λ -Scale calculus, it expresses the fact that in emergent algebras the operation indexed with the neutral element 1 of the group Γ has the property x ◦ 1 y = y .
<details>
<summary>Image 16 Details</summary>
### Visual Description
## Diagram: Feynman Diagram Transformation
### Overview
The image shows a transformation of a Feynman diagram. The diagram on the left represents a vertex with three lines connected to it, labeled 1, 2, and 3. The diagram on the right shows a modified version of the same vertex, where one of the lines is cut and reconnected in a different way. The transformation is indicated by a curved arrow labeled "ext 2".
### Components/Axes
* **Diagram 1 (Left):**
* A central vertex represented by a circle containing the number "1".
* Three lines emanating from the vertex.
* Each line has an arrow indicating direction.
* The lines are labeled 1, 2, and 3 in red.
* **Diagram 2 (Right):**
* Two lines emanating from the bottom, labeled 1 and 2 in red.
* A vertical line at the top, labeled 3 in red.
* A short horizontal line intersecting the line labeled 1.
* **Transformation Arrow:**
* A curved blue arrow labeled "ext 2" pointing from the top line of the left diagram to the top line of the right diagram.
### Detailed Analysis or ### Content Details
**Diagram 1 (Left):**
* Line 1: Originates from the bottom-left, pointing towards the central vertex.
* Line 2: Originates from the bottom-right, pointing towards the central vertex.
* Line 3: Originates from the top, pointing towards the central vertex.
**Diagram 2 (Right):**
* Line 1: Originates from the bottom-left, pointing upwards and is cut by a short horizontal line.
* Line 2: Originates from the bottom-right, pointing upwards.
* Line 3: Originates from the top, pointing downwards and connects to line 2.
**Transformation Arrow:**
* The blue arrow labeled "ext 2" indicates a transformation or modification of the diagram.
### Key Observations
* The transformation involves cutting and reconnecting one of the lines (line 1) in the diagram.
* The arrow labeled "ext 2" suggests an external operation or modification.
* The numbers 1, 2, and 3 likely represent different particles or states.
### Interpretation
The image illustrates a manipulation of a Feynman diagram, a tool used in theoretical physics to represent particle interactions. The transformation, indicated by "ext 2", modifies the connectivity of the diagram, potentially representing a different physical process or a different way of calculating the same process. The cutting and reconnecting of line 1 suggests a change in the interaction or propagation of the particle represented by that line. The diagram likely represents a step in a calculation or a specific interaction within a larger physical model.
</details>
2.6. Local pruning. Local pruning moves are local moves which eliminate 'dead' edges. Notice that, unlike the previous moves, these are one-way (you can eliminate dead edges, but not add them to graphs).
<details>
<summary>Image 17 Details</summary>
### Visual Description
## Diagram: LOC Pruning Transformations
### Overview
The image depicts two diagrams illustrating "LOC PRUNING" transformations. Each diagram shows a transformation from a more complex structure to a simpler one, indicated by a curved arrow labeled "LOC PRUNING". The diagrams involve lines, arrows indicating direction, and circles containing symbols.
### Components/Axes
* **Diagram 1 (Top)**:
* A central node (circle) containing the symbol "λ".
* Three lines emanating from the node. Two lines point upwards and outwards, each terminating with a short perpendicular line. One line points downwards. All three lines have arrows indicating direction away from the central node.
* A single vertical line with an upward-pointing arrow and a short perpendicular line at the top.
* A curved arrow labeled "LOC PRUNING" pointing from the complex structure to the single line.
* **Diagram 2 (Bottom)**:
* A single vertical line with an upward-pointing arrow, labeled "1" at the bottom and "2" at the top.
* A node (circle) containing the symbol "Y".
* Three lines connected to the node. One line points downwards, labeled "1" at the bottom. One line points upwards, labeled "2" at the top. One line points to the left, terminating with a short perpendicular line. All three lines have arrows indicating direction away from the central node.
* A curved arrow labeled "LOC PRUNING" pointing from the complex structure to the single line.
### Detailed Analysis
* **Diagram 1**:
* The central node has three outgoing lines. The two upper lines are terminated with a short perpendicular line, indicating an external connection or constraint.
* The "LOC PRUNING" transformation simplifies this structure to a single outgoing line.
* **Diagram 2**:
* The single line is labeled with "1" at the bottom and "2" at the top, indicating a direction or flow from 1 to 2.
* The complex structure has a node with three outgoing lines. The left line is terminated with a short perpendicular line.
* The "LOC PRUNING" transformation simplifies this structure to a single line with the same directionality.
### Key Observations
* Both diagrams illustrate a simplification process labeled "LOC PRUNING".
* The complex structures involve nodes with three outgoing lines, one or more of which are terminated with a short perpendicular line.
* The simplified structures are single lines with a defined direction.
### Interpretation
The diagrams likely represent a simplification or reduction process in a system or model. "LOC PRUNING" seems to be a method for reducing complex structures to simpler, linear representations. The short perpendicular lines may indicate external constraints or connections that are removed during the pruning process. The symbols "λ" and "Y" within the nodes might represent specific types of nodes or operations being simplified. The numbers "1" and "2" in the second diagram likely represent input and output, or a direction of flow.
</details>
<details>
<summary>Image 18 Details</summary>
### Visual Description
## Diagram: LOC Pruning Examples
### Overview
The image illustrates the concept of "LOC PRUNING" through three separate examples. Each example shows an initial state with connected components and a subsequent state after pruning, indicated by a curved arrow labeled "LOC PRUNING".
### Components/Axes
* **Nodes:** Represented by circles, some containing symbols (ε, a circle with a cross inside, and a line with a perpendicular line above it).
* **Edges:** Represented by lines with arrowheads, indicating direction.
* **Labels:** Numerical labels "1" and "2" are associated with the edges.
* **Text Labels:** "LOC PRUNING" is written in blue text with an arrow indicating the transformation.
### Detailed Analysis
**Example 1 (Top):**
* Initial state: A node containing the symbol "ε" connects to two edges, labeled "1" and "2".
* Pruning: "LOC PRUNING" transforms this into two separate edges, labeled "1" and "2", each with a short perpendicular line above the arrow.
**Example 2 (Middle):**
* Initial state: A node containing a circle with a cross inside connects to two edges, labeled "1" and "2".
* Pruning: "LOC PRUNING" transforms this into two separate edges, labeled "1" and "2", each with a short perpendicular line above the arrow.
**Example 3 (Bottom):**
* Initial state: A node represented by a line with a perpendicular line above it, enclosed in a dashed red circle.
* Pruning: "LOC PRUNING" transforms this into an empty dashed red circle.
### Key Observations
* "LOC PRUNING" appears to disconnect nodes and edges.
* The specific symbol within the node in the initial state seems to be irrelevant to the pruning process.
* The dashed red circles in the third example suggest a region or scope being pruned.
### Interpretation
The diagram illustrates a process called "LOC PRUNING," which involves removing connections or elements from a network or system. The examples show different initial configurations being transformed into disconnected components or empty regions. The "LOC PRUNING" label suggests that this process is localized, potentially focusing on specific areas or components within a larger system. The red dashed circles may indicate the scope or boundary of the pruning operation. The diagram does not provide specific details about the criteria or mechanisms for pruning, but it visually represents the outcome of the process.
</details>
Global moves or conditions. Global moves are those which are not local, either because the condition C applies to parts of the graph which may have an arbitrary large sum or edges plus nodes, or because after the move the graph P ′ which replaces the graph P has an arbitrary large sum or edges plus nodes.
2.7. (ext1) move. This corresponds to the rule (ext1) from λ -Scale calculus, or to η -reduction in lambda calculus (see theorem 3.1, part (e) for details). It involves a λ graph (think about the λ abstraction operation in lambda calculus) and a graph (think about the application operation in lambda calculus).
The rule is: if there is no oriented path from '2' to '1', then the following move can be performed.
<details>
<summary>Image 19 Details</summary>
### Visual Description
## Diagram: Diagram of a Transformation
### Overview
The image shows a diagram illustrating a transformation of a complex loop structure into a simple vertical line. The diagram consists of two main parts connected by a blue, curved, double-headed arrow labeled "ext 1". The left side depicts a loop with internal nodes, while the right side shows a straight line. Arrows indicate the direction of flow or transformation.
### Components/Axes
* **Left Side:** A complex loop structure with two nodes.
* Node 1: Contains the Greek letter lambda (λ).
* Node 2: Contains a three-pronged symbol.
* The loop has arrows indicating direction.
* The bottom of the loop is labeled "1".
* The top of the loop is labeled "2".
* **Right Side:** A straight vertical line with an arrow indicating direction.
* The bottom of the line is labeled "1".
* The top of the line is labeled "2".
* **Connector:** A blue, curved, double-headed arrow labeled "ext 1" connects the left and right sides, indicating a transformation.
### Detailed Analysis or ### Content Details
* **Left Side Loop:**
* The loop starts at the bottom, labeled "1".
* The loop splits into two paths.
* One path goes to the node containing lambda (λ).
* The other path goes to the node containing the three-pronged symbol.
* The paths rejoin and exit at the top, labeled "2".
* Arrows along the paths indicate the direction of flow.
* **Right Side Line:**
* A straight vertical line starts at the bottom, labeled "1".
* An arrow indicates the direction of flow upwards.
* The line ends at the top, labeled "2".
* **Transformation:**
* The blue, curved, double-headed arrow labeled "ext 1" indicates a transformation from the complex loop structure on the left to the simple vertical line on the right.
### Key Observations
* The diagram illustrates a simplification or transformation of a complex structure into a simpler one.
* The labels "1" and "2" likely represent input and output points, respectively.
* The nodes within the loop on the left likely represent specific operations or components.
* The "ext 1" label suggests an external operation or transformation.
### Interpretation
The diagram likely represents a mathematical or physical process where a complex system or interaction (represented by the loop structure) is simplified or transformed into a more basic form (represented by the straight line). The "ext 1" label suggests that this transformation is achieved through an external operation or interaction. The nodes containing lambda (λ) and the three-pronged symbol likely represent specific parameters or components within the system that are affected by the transformation. The arrows indicate the direction of flow or transformation, suggesting a process that moves from input "1" to output "2".
</details>
2.8. (Global FAN-OUT) move. This is a global move, because it consists in replacing (under certain circumstances) a graph by two copies of that graph.
The rule is: if a graph in G ∈ GRAPH has a Υ bottleneck, that is if we can find a sub-graph A ∈ GRAPH connected to the rest of the graph G only through a Υ gate, then we can perform the move explained in the next figure, from the left to the right.
Conversely, if in the graph G we can find two identical subgraphs (denoted by A ), which are in GRAPH , which have no edge connecting one with another and which are connected to the rest of G only through one edge, as in the RHS of the figure, then we can perform the move from the right to the left.
<details>
<summary>Image 20 Details</summary>
### Visual Description
## Diagram: Global Fan-Out
### Overview
The image depicts a diagram illustrating a "GLOBAL FAN-OUT" process. It shows two circular regions connected by a curved arrow, representing a transformation or relationship between the two states. The left circle contains a central node with three incoming and outgoing connections, while the right circle shows two separate connections.
### Components/Axes
* **Circles:** Two dashed red circles, one on the left and one on the right. These circles likely represent a system or boundary.
* **Arrows:** Black arrows indicate the direction of flow or interaction.
* **Nodes:** The left circle contains a central node with a "Y" shape inside a circle.
* **Labels:** The numbers "1" and "2" are present at the ends of the lines entering/exiting the circles. The letter "A" is present near the bottom of each circle.
* **Connecting Arrow:** A blue curved arrow connects the two circles, pointing from left to right.
* **Text:** The text "GLOBAL FAN-OUT" is located below the connecting arrow.
### Detailed Analysis
**Left Circle:**
* Two lines labeled "1" and "2" enter the circle from the top-left and top-right, respectively. Each line has an arrow indicating flow towards the central node.
* The central node is a circle containing a "Y" shape.
* One line exits the circle from the bottom of the central node, with an arrow pointing downwards.
* The letter "A" is located below the exiting line.
**Right Circle:**
* Two lines exit the circle from the top-left and top-right, labeled "1" and "2" respectively. Each line has an arrow pointing away from the center of the circle.
* The letter "A" is located near the base of each line.
**Connecting Arrow:**
* A blue curved arrow connects the right side of the left circle to the left side of the right circle.
* The text "GLOBAL FAN-OUT" is located below the arrow.
### Key Observations
* The left circle represents a convergence of two inputs into a single output.
* The right circle represents a divergence of two outputs.
* The "GLOBAL FAN-OUT" process transforms a single output into two separate outputs.
### Interpretation
The diagram illustrates a "GLOBAL FAN-OUT" process, where a single input "A" (represented by the output of the left circle) is transformed into two separate outputs "A" (represented by the outputs of the right circle). The central node in the left circle likely represents a processing or distribution point. The numbers "1" and "2" could represent different channels or destinations for the outputs. The diagram suggests a system where a single signal or resource is distributed to multiple recipients.
</details>
Remark that (global FAN-OUT) trivially implies (CO-COMM). ( As an local rule alternative to the global FAN-OUT, we might consider the following. Fix a number N and consider only graphs A which have at most N (nodes + arrows). The N LOCAL FAN-OUT move is the same as the GLOBAL FAN-OUT move, only it applies only to such graphs A . This local FAN-OUT move does not imply CO-COMM.)
2.9. Global pruning. This a global move which eliminates 'dead' edges.
The rule is: if a graph in G ∈ GRAPH has a ending, that is if we can find a sub-graph A ∈ GRAPH connected only to a gate, with no edges connecting to the rest of G , then we can erase this graph and the respective gate.
<details>
<summary>Image 21 Details</summary>
### Visual Description
## Diagram: Global Pruning
### Overview
The image is a diagram illustrating a process labeled "GLOBAL PRUNING". It shows a transition from a state represented by a circle containing a symbol and the letter "A" to another state represented by an empty circle. The transition is indicated by a curved arrow.
### Components/Axes
* **Circles:** Two circles, both with dashed red outlines. The left circle contains a symbol and the letter "A". The right circle is empty.
* **Symbol:** Inside the left circle, there is a symbol consisting of a horizontal line with a vertical arrow pointing downwards.
* **Letter:** The letter "A" is located below the arrow in the left circle.
* **Arrow:** A curved blue arrow points from the bottom of the left circle to the center of the right circle.
* **Label:** The text "GLOBAL PRUNING" is written in blue below the arrow.
### Detailed Analysis or ### Content Details
* **Left Circle:** Contains a symbol resembling a T-shaped structure with an arrow pointing down from the center of the horizontal line. The letter "A" is positioned directly below the arrow.
* **Right Circle:** Is empty, indicating a state after the "GLOBAL PRUNING" process.
* **Arrow and Label:** The blue arrow indicates the direction of the process, and the label "GLOBAL PRUNING" describes the action being performed.
### Key Observations
* The diagram illustrates a transformation or reduction process.
* The symbol and the letter "A" in the left circle are removed or altered during the "GLOBAL PRUNING" process, resulting in an empty circle on the right.
### Interpretation
The diagram represents a process called "GLOBAL PRUNING" where an initial state, represented by the circle containing the symbol and the letter "A", is transformed into a final state, represented by the empty circle. The "GLOBAL PRUNING" process likely involves the removal or simplification of elements, as indicated by the transition from a state with content to a state with no content. The symbol and the letter "A" are likely being pruned or removed during this process.
</details>
The global pruning may be needed because of the λ gates, which cannot be removed only by local pruning.
2.10. Elimination of loops. It is possible that, after using a local or global move, we obtain a graph with an arrow which closes itself, without being connected to any node. Here is an example, concerning the application of the graphic β move. We may erase any such loop, or add one.
λ GRAPHS. The edges of an elementary graph λ can be numbered unambiguously, clockwise, by 1, 2, 3, such that 1 is the number of the entrant edge.
Definition 2.4 A graph G ∈ GRAPH is a λ -graph, notation G ∈ λGRAPH , if:
- -it does not have ¯ ε gates,
- -for any node λ any oriented path in G starting at the edge 2 of this node can be completed to a path which either terminates in a graph , or else terminates at the edge 1 of this node.
The condition G ∈ λGRAPH is global, in the sense that in order to decide if G ∈ λGRAPH we have to examine parts of the graph which may have an arbitrary large sum or edges plus nodes.
## 3 Conversion of lambda terms into GRAPH
Here I show how to associate to a lambda term a graph in GRAPH , then I use this to show that β -reduction in lambda calculus transforms into the β rule for GRAPH . (Thanks to Morita Yasuaki for some corrections.)
Indeed, to any term A ∈ T ( X ) (where T ( X ) is the set of lambda terms over the variable set X ) we associate its syntactic tree. The syntactic tree of any lambda term is constructed by using two gates, one corresponding to the λ abstraction and the other corresponding to the application. We draw syntactic trees with the leaves (elements of X ) at the bottom and the root at the top. We shall use the following notation for the two gates: at the left is the gate for the λ abstraction and at the right is the gate for the application.
<details>
<summary>Image 22 Details</summary>
### Visual Description
## Diagram: Lambda Calculus and Application
### Overview
The image presents two diagrams illustrating concepts from lambda calculus: abstraction (left) and application (right). Both diagrams use a tree-like structure with arrows indicating the flow or transformation of terms.
### Components/Axes
**Left Diagram (Abstraction):**
* **Top:** `λx.A` (Lambda abstraction of variable x from term A)
* **Center:** A circle containing the lambda symbol `λ`. This represents the abstraction operation.
* **Bottom-Left:** `x` (Variable x)
* **Bottom-Right:** `A` (Term A)
* **Arrows:** Arrows point from `x` and `A` towards the circle containing `λ`, and then from the circle upwards towards `λx.A`.
**Right Diagram (Application):**
* **Top:** `AB` (Application of term A to term B)
* **Center:** A circle containing an upside-down `Y` symbol. This represents the application operation.
* **Bottom-Left:** `A` (Term A)
* **Bottom-Right:** `B` (Term B)
* **Arrows:** Arrows point from `A` and `B` towards the circle containing the upside-down `Y`, and then from the circle upwards towards `AB`.
### Detailed Analysis
**Left Diagram (Abstraction):**
The diagram shows how a lambda abstraction `λx.A` is formed. The variable `x` and the term `A` are inputs to the abstraction operation (represented by the circle with `λ`), which combines them to produce the lambda expression `λx.A`.
**Right Diagram (Application):**
The diagram shows the application of term `A` to term `B`, resulting in `AB`. The terms `A` and `B` are inputs to the application operation (represented by the circle with the upside-down `Y`), which combines them to produce the application `AB`.
### Key Observations
* Both diagrams use a similar structure to represent operations in lambda calculus.
* The arrows indicate the direction of transformation or flow of terms.
* The symbols within the circles represent the specific operations being performed (abstraction and application).
### Interpretation
The diagrams visually represent fundamental operations in lambda calculus. The left diagram illustrates how a function is created by abstracting a variable from a term. The right diagram illustrates how a function (represented by a term) is applied to an argument (another term). These diagrams are useful for understanding the basic building blocks of lambda calculus and how complex expressions can be constructed from simpler ones.
</details>
Remark that these two gates are from the graphical alphabet of GRAPH , but the syntactic tree is decorated: at the bottom we have leaves from X . Also, remark the peculiar orientation of the edge from the left (in tree notation convention) of the λ gate. For the moment, this orientation is in contradiction with the implicit orientation (from down-up) of edges of the syntactic tree, but soon this matter will become clear.
We shall remove all leaves decorations, with the price of introducing new gates, namely Υ and gates. This will be done in a sequence of steps, detailed further. Take the syntactic tree of A ∈ T ( X ), drawn with the mentioned conventions (concerning gates and the positioning of leaves and root respectively).
We take as examples the following five lambda terms: I = λx.x , K = λx. ( λy.x ), S = λx. ( λy. ( λz. (( xz )( yz )))), Ω = ( λx. ( xx ))( λx. ( xx )) and T = ( λx. ( xy ))( λx. ( xy )).
Step 1. Elimination of bound variables, part I. Any leaf of the tree is connected to the root by an unique path.
Start from the leftmost leaf, perform the algorithm explained further, then go to the right and repeat until all leaves are exhausted. We initialize also a list B = ∅ of bound variables.
Take a leaf, say decorated with x ∈ X . To this leaf is associated a word (a list) which is formed by the symbols of gates which are on the path which connects (from the bottom-up) the leaf with the root, together with information about which way, left (L) or right (R), the path passes through the gates. Such a word is formed by the letters λ L , λ R , L , R .
If the first letter is λ L then add to the list B the pair ( x, w ( x )) formed by the variable name x , and the associated word (describing the path to follow from the respective leaf to the root). Then pass to a new leaf.
Else continue along the path to the roof. If we arrive at a λ gate, this can happen only coming from the right leg of the λ gate, thus we can find only the letter λ R . In such a case look at the variable y which decorates the left leg of the same λ gate. If x = y then add to the syntactic tree a new edge, from y to x and proceed further along the path, else proceed further. If the root is attained then pass to next leaf.
Examples: the graphs associated to the mentioned lambda terms, together with the list of bound variables, are the following.
$$\begin{array} { r l } & { - I \, = \, \lambda x . x \, h a s \, B \, = \, \left \{ ( x , \lambda ^ { L } ) \right \} , \, K \, = \, \lambda x . ( \lambda y . x ) \, h a s \, B \, = \, \left \{ ( x , \lambda ^ { L } ) , ( y , \lambda ^ { L } \lambda ^ { R } ) \right \} , \, S \, = } \\ & { \quad \lambda x . ( \lambda y . ( \lambda z . ( ( x z ) ( y z ) ) ) ) \, h a s \, B = \left \{ ( x , \lambda ^ { L } ) , ( y , \lambda ^ { L } \lambda ^ { R } ) , ( z , \lambda ^ { L } \lambda ^ { R } \lambda ^ { R } ) \right \} . } \end{array}$$
<details>
<summary>Image 23 Details</summary>
### Visual Description
## Diagram: Lambda Calculus Reduction
### Overview
The image depicts three diagrams illustrating the reduction process in lambda calculus. Each diagram shows a lambda expression represented as a tree structure, with nodes labeled with "λ" or a symbol resembling a "fork". Red arrows indicate the reduction steps, showing how variables are substituted and the expression is simplified.
### Components/Axes
* **Nodes:** Circular nodes labeled with "λ" represent lambda abstractions. Nodes with a "fork" symbol represent applications.
* **Edges:** Black arrows represent the structure of the lambda expression, indicating function application and variable binding. Red arrows indicate the reduction steps.
* **Variables:** Variables are labeled as x, y, and z.
* **Direction:** The black arrows point downwards, indicating the flow of function application. The red arrows show the direction of the reduction process.
### Detailed Analysis
**Diagram 1 (Left):**
* A lambda abstraction (λ) at the top.
* Two branches extending downwards, each labeled "x".
* A red arrow starts from the left "x", curves downwards, and points to the right "x", indicating a substitution.
**Diagram 2 (Middle):**
* A lambda abstraction (λ) at the top.
* Two branches extending downwards. The left branch is labeled "x".
* The right branch leads to another lambda abstraction (λ).
* From the second lambda abstraction, two branches extend downwards, labeled "y" and "x".
* A red arrow starts from "x", curves downwards, and points to "y", indicating a substitution.
**Diagram 3 (Right):**
* A lambda abstraction (λ) at the top.
* A horizontal line connects the top lambda abstraction to two more lambda abstractions (λ).
* From the rightmost lambda abstraction, a branch extends downwards to a "fork" node.
* The variables x, y, and z are connected to the top lambda abstractions.
* The "fork" node has two branches, each leading to another "fork" node.
* Each of the lower "fork" nodes has three branches extending downwards.
* The variables at the bottom are labeled "x", "z", "y", and "z".
* Red arrows connect "x" to "x", "y" to "z", and "z" to "y" and "z", indicating substitutions.
### Key Observations
* The diagrams illustrate the process of beta reduction in lambda calculus.
* The red arrows show how variables are replaced during the reduction process.
* The complexity of the lambda expression increases from left to right.
### Interpretation
The diagrams demonstrate how lambda expressions are simplified through a series of substitutions. The first diagram shows a simple self-application. The second diagram introduces a nested lambda abstraction. The third diagram shows a more complex expression with multiple applications and substitutions. The red arrows visually represent the core mechanism of beta reduction, which is the foundation of computation in lambda calculus. The increasing complexity from left to right suggests a step-by-step illustration of how more intricate lambda expressions can be reduced.
</details>
$$\begin{array} { r l } & { - \Omega = ( \lambda x . ( x x ) ) ( \lambda x . ( x x ) ) h a s B = \left \{ ( x , \lambda ^ { L } \lambda ^ { L } ) , ( x , \lambda ^ { L } \lambda ^ { R } ) \right \} , T = ( \lambda x . ( x y ) ) ( \lambda x . ( x y ) ) h a s } \\ & { B = \left \{ ( x , \lambda ^ { L } \lambda ^ { L } ) , ( x , \lambda ^ { L } \lambda ^ { R } ) \right \} . } \end{array}$$
Step 2. Elimination of bound variables, part II. We have now a list B of bound variables. If the list is empty then go to the next step. Else, do the following, starting from the first element of the list, until the list is finished.
<details>
<summary>Image 24 Details</summary>
### Visual Description
## Diagram: Tree Diagrams with Redirection
### Overview
The image presents two tree diagrams, each depicting a hierarchical structure with nodes and directed edges. The diagrams are similar but differ in the final nodes and the redirection of edges indicated by red arrows. The nodes are labeled with symbols and variables.
### Components/Axes
* **Nodes:** Circular nodes containing symbols. The symbols are either "λ" (lambda) or a symbol resembling a trident inside a circle.
* **Edges:** Directed edges (arrows) connecting the nodes, indicating the flow or relationship between them.
* **Variables:** The terminal nodes are labeled with variables "x" and "y".
* **Redirection Arrows:** Red arrows indicate a redirection or mapping from one terminal node to another.
### Detailed Analysis
**Left Diagram:**
* **Top Node:** A circular node with the trident symbol.
* **Second Level:** Two nodes, each labeled with "λ".
* **Third Level:** Two nodes, each with the trident symbol.
* **Terminal Nodes:** Each trident node splits into two terminal nodes labeled "x".
* **Redirection:** A red arrow originates from the leftmost "x" and curves to point to the second "x" from the left. Another red arrow originates from the third "x" from the left and curves to point to the rightmost "x".
**Right Diagram:**
* **Top Node:** A circular node with the trident symbol.
* **Second Level:** Two nodes, each labeled with "λ".
* **Third Level:** Two nodes, each with the trident symbol.
* **Terminal Nodes:** The left trident node splits into "x" and "y". The right trident node splits into "x" and "y".
* **Redirection:** A red arrow originates from the leftmost "x" and curves to point to the "x" on the right side. Another red arrow originates from the "y" on the left side and curves to point to the "y" on the right side.
### Key Observations
* Both diagrams share the same initial structure, diverging only at the terminal nodes and redirection arrows.
* The left diagram maps "x" to "x", while the right diagram maps "x" to "x" and "y" to "y".
### Interpretation
The diagrams likely represent some form of transformation or mapping process. The "λ" nodes might represent lambda abstractions, and the trident nodes could represent function applications or other operations. The red arrows indicate a specific mapping or substitution rule. The left diagram shows a mapping where all terminal nodes are "x" and are redirected to each other. The right diagram shows a mapping where "x" maps to "x" and "y" maps to "y", suggesting an identity-like transformation for these variables. The diagrams could be related to lambda calculus, type theory, or other formal systems where such transformations are common.
</details>
An element, say ( x, w ( x )), of the list, is either connected to other leaves by one or more edges added at step 1, or not. If is not connected then erase the variable name with the associated path w ( x ) and replace it by a gate. If it is connected then erase it, replace it by a tree formed by Υ gates, which starts at the place where the element of the list were before the erasure and stops at the leaves which were connected to x . Erase all decorations which were joined to x and also erase all edges which were added at step 1 to the leave x from the list.
Examples: after the step 2, the graphs associated to the mentioned lambda terms are the following.
- -the graphs of I = λx.x , K = λx. ( λy.x ), S = λx. ( λy. ( λz. (( xz )( yz )))) are
- -the graphs of Ω = ( λx. ( xx ))( λx. ( xx )), T = ( λx. ( xy ))( λx. ( xy )) are
<details>
<summary>Image 25 Details</summary>
### Visual Description
## Diagram: Lambda Calculus Reduction
### Overview
The image presents three diagrams illustrating the reduction process in lambda calculus. Each diagram depicts a lambda expression and its reduction steps using directed edges to show the flow of computation. The diagrams increase in complexity from left to right, demonstrating different reduction scenarios.
### Components/Axes
* **Nodes:** Represented by circles, each containing the Greek letter lambda (λ), indicating a lambda abstraction. Other nodes contain a symbol resembling a trident.
* **Edges:** Directed lines with arrows indicating the direction of reduction or application.
* **Input/Output:** Each diagram has an input arrow at the top and output arrows at the bottom.
* **Bound Variable Indicator:** A short horizontal line indicates a bound variable.
### Detailed Analysis
**Diagram 1 (Left):**
* A single lambda node (λ) at the top.
* An input arrow points towards the lambda node.
* Two arrows originate from the lambda node, pointing downwards.
* These two arrows converge into a single, curved arrow that loops back to the lambda node.
* An output arrow points downwards from the loop.
**Diagram 2 (Middle):**
* A lambda node (λ) at the top with an input arrow.
* Two arrows originate from the top lambda node.
* One arrow points downwards to another lambda node (λ).
* The second arrow curves downwards and to the left, forming a loop that returns to the top lambda node.
* A short horizontal line (bound variable indicator) is present on the arrow pointing downwards from the second lambda node.
* An output arrow points downwards from the second lambda node.
**Diagram 3 (Right):**
* Three lambda nodes (λ) are connected horizontally at the top, with arrows pointing from left to right. An input arrow points to the leftmost lambda node.
* The rightmost lambda node has an arrow pointing downwards to a node containing a trident symbol.
* Two arrows originate from the leftmost lambda node, curving downwards and to the right, and connecting to the bottom trident node.
* Two arrows originate from the middle lambda node, curving downwards and to the right, and connecting to the bottom trident node.
* The trident node has three arrows pointing downwards to three trident nodes.
* Each of these three trident nodes has an output arrow pointing downwards.
### Key Observations
* The diagrams illustrate the reduction of lambda expressions, showing how lambda abstractions are applied and how variables are bound.
* The complexity increases from left to right, demonstrating more intricate reduction scenarios.
* The trident symbol likely represents a specific operation or term within the lambda calculus.
### Interpretation
The diagrams visually represent the process of lambda calculus reduction. The lambda nodes represent functions, and the arrows indicate the flow of data and application of these functions. The loops suggest recursive or iterative processes. The trident symbol likely represents a specific operator or data structure being manipulated within the lambda expressions. The increasing complexity of the diagrams suggests a progression from simple to more complex lambda expressions and their corresponding reduction steps. The diagrams provide a visual aid for understanding the abstract concepts of lambda calculus and its reduction rules.
</details>
<details>
<summary>Image 26 Details</summary>
### Visual Description
## Diagram: Graph Representations of Lambda Calculus Expressions
### Overview
The image presents two directed graph representations of lambda calculus expressions. Each graph consists of nodes labeled with symbols (λ, ⋎) and directed edges indicating the flow of computation. The left graph represents a more complex expression with branching, while the right graph represents a simpler expression with self-reference.
### Components/Axes
* **Nodes:** Represented by circles containing symbols. The symbols are:
* λ (lambda): Represents lambda abstraction.
* ⋎: Represents application.
* y: Represents a free variable.
* **Edges:** Represented by arrows, indicating the direction of computation or data flow.
### Detailed Analysis
**Left Graph:**
* **Top Node:** A single ⋎ node at the top, with an outgoing arrow.
* **Second Level:** Two λ nodes, each connected to the top ⋎ node by an arrow.
* **Third Level:** Each λ node connects to two ⋎ nodes.
* **Bottom Level:** The two ⋎ nodes connected to each λ node are interconnected with arrows forming a loop.
**Right Graph:**
* **Top Node:** A single ⋎ node at the top, with an outgoing arrow.
* **Second Level:** Two λ nodes, each connected to the top ⋎ node by an arrow.
* **Third Level:** Each λ node connects to a ⋎ node.
* **Bottom Level:** Each ⋎ node has an outgoing arrow labeled "y" and a self-loop arrow.
### Key Observations
* The ⋎ symbol seems to represent function application, while λ represents lambda abstraction.
* The arrows indicate the direction of data flow or computation.
* The left graph represents a more complex expression with branching and interconnected nodes.
* The right graph represents a simpler expression with self-reference (loops) and free variables (y).
### Interpretation
The diagrams illustrate how lambda calculus expressions can be represented as directed graphs. The nodes represent operations (abstraction and application), and the edges represent the flow of data or computation. The left graph likely represents a more complex expression involving multiple applications and abstractions, while the right graph represents a simpler expression with self-application, potentially related to recursion or fixed-point combinators. The "y" labels in the right graph indicate free variables, which are variables not bound by any lambda abstraction within the expression. The self-loops in the right graph suggest a recursive process where the output of an application is fed back into itself.
</details>
Remark that at this step the necessity of having the peculiar orientation of the left leg of the λ gate becomes clear.
Remark also that there may be more than one possible tree of gates Υ, at each elimination of a bound variable (in case a bound variable has at least tree occurrences). One may use any tree of Υ which is fit. The problem of multiple possibilities is the reason of introducing the (CO-ASSOC) move.
Step 3. We may still have leaves decorated by free variables. Starting from the left to the right, group them together in case some of them occur in multiple places, then replace the multiple occurrences of a free variable by a tree of Υ gates with a free root, which ends exactly where the occurrences of the respective variable are. Again, there are multiple ways of doing this, but we may pass from one to another by a sequence of (CO-ASSOC) moves.
Examples: after the step 3, all the graphs associated to the mentioned lambda terms, excepting the last one, are left unchanged. The graph of the last term, changes.
- -as an illustration, I figure the graphs of Ω = ( λx. ( xx ))( λx. ( xx )), left unchanged by step 3, and the graph of T = ( λx. ( xy ))( λx. ( xy )):
<details>
<summary>Image 27 Details</summary>
### Visual Description
## Diagram: Directed Graphs
### Overview
The image presents two distinct directed graphs, each composed of nodes and directed edges (arrows). The nodes are represented as circles, some containing the symbol "λ" and others containing a symbol resembling a trident or a stylized "Y". The arrows indicate the direction of flow or relationship between the nodes. The graphs differ in their structure and connectivity.
### Components/Axes
* **Nodes:** Circles containing either "λ" or a trident-like symbol.
* **Edges:** Arrows indicating direction.
* **Graph 1 (Left):** A tree-like structure with a root node at the top, branching down to two "λ" nodes, each further branching to a cycle of three trident nodes.
* **Graph 2 (Right):** A tree-like structure with a root node at the top, branching down to two "λ" nodes, each connected to a trident node. These trident nodes are then connected to a single trident node at the bottom.
### Detailed Analysis or ### Content Details
**Graph 1 (Left):**
* **Top Node:** A circle containing the trident symbol. An arrow points upwards from this node.
* **Second Level:** Two nodes, each containing "λ". Arrows point from the top node to each of these "λ" nodes.
* **Third Level:** Each "λ" node connects to a cycle of three trident nodes. The arrows form a closed loop within each cycle.
**Graph 2 (Right):**
* **Top Node:** A circle containing the trident symbol. An arrow points upwards from this node.
* **Second Level:** Two nodes, each containing "λ". Arrows point from the top node to each of these "λ" nodes.
* **Third Level:** Each "λ" node connects to a trident node.
* **Bottom Node:** A single trident node. Arrows point from the trident nodes in the third level to this bottom node. An arrow points downwards from this node. Additionally, there are curved arrows looping back from the third level trident nodes to themselves.
### Key Observations
* Both graphs share a similar initial structure: a top trident node branching to two "λ" nodes.
* The key difference lies in the connectivity of the nodes below the "λ" nodes. Graph 1 features cycles, while Graph 2 features loops and a converging structure.
### Interpretation
The diagrams likely represent some form of process or relationship, where the nodes represent states or entities, and the arrows represent transitions or dependencies. The "λ" symbol might indicate a specific type of operation or transformation. The cycles in Graph 1 could represent iterative processes, while the converging structure in Graph 2 could represent a consolidation or aggregation. The loops in Graph 2 could represent self-referential processes. Without further context, the precise meaning of these graphs remains abstract.
</details>
Theorem 3.1 Let A ↦→ [ A ] be a transformation of a lambda term A into a graph [ A ] as described previously (multiple transformations are possible because of the choice of Υ trees). Then:
- (a) for any term A the graph [ A ] is in λGRAPH ,
- (b) if [ A ] ′ and [ A ]' are transformations of the term A then we may pass from [ A ] ′ to [ A ]' by using a finite number (exponential in the number of leaves of the syntactic tree of A ) of (CO-ASSOC) moves,
- (c) if B is obtained from A by α -conversion then we may pass from [ A ] to [ B ] by a finite sequence of (CO-ASSOC) moves,
- (d) let A,B ∈ T ( X ) be two terms and x ∈ X be a variable. Consider the terms λx.A and A [ x := B ] , where A [ x := B ] is the term obtained by substituting in A the free occurrences of x by B . We know that β reduction in lambda calculus consists in passing from ( λx.A ) B to A [ x := B ] . Then, by one β move in GRAPH applied to [( λx.A ) B ] we pass to a graph which can be further transformed into one of A [ x := B ] , via (global FAN-OUT) moves, (CO-ASSOC) moves and pruning moves,
- (e) with the notations from (d), consider the terms A and λx.Ax with x ∈ FV ( A ) ; then the η reduction, consisting in passing from λx.Ax to A , corresponds to the ext1 move applied to the graphs [ λx.Ax ] and [ A ] .
Proof. (a) we have to prove that for any node λ any oriented path in [ A ] starting at the left exiting edge of this node can be completed to a path which either terminates in a graph , or else terminates at the entry peg of this node, but this is clear. Indeed, either the bound variable (of this λ node in the syntactic tree of A ) is fresh, then the bound variable is replaced by a gate, or else, the bound variable is replaced by a tree of Υ gates. No matter which path we choose, we may complete it to a cycle passing by the said λ node.
(b) Clear also, because the (CO-ASSOC) move is designed for passing from a tree of Υ gates to another tree with the same number of leaves.
(c) Indeed, the names of bound variables of A do not affect the construction of [ A ], therefore if B is obtained by α -conversion of A , then [ B ] differs from [ A ] only by the particular choice of trees of Υ gates. But this is solved by (CO-ASSOC) moves.
(d) This is the surprising, maybe, part of the theorem. There are two cases: x is fresh for A or not. If x is fresh for A then in the graph [( λx.A ) B ] the name variable x is replaced by a gate. If not, then all the occurrences of x in A are connected by a Υ tree with root at the left peg of the λ gate where x appears as a bound variable.
In the case when x is not fresh for A , we see in the LHS of the figure the graph [( λx.A ) B ] (with a remanent decoration of 'x'). We perform a graphic ( β ) move and we obtain the graph from the right.
<details>
<summary>Image 28 Details</summary>
### Visual Description
## Diagram: Beta Transformation
### Overview
The image presents a diagram illustrating a transformation, labeled "β", between two configurations of a network or graph. Each configuration consists of nodes, edges (represented by lines with arrows indicating direction), and labeled points. The transformation rearranges the connections and spatial arrangement of these elements.
### Components/Axes
* **Nodes:** Represented by circles or rounded shapes, labeled with symbols (λ, A) or graphical elements.
* **Edges:** Represented by lines with arrowheads, indicating the direction of flow or connection.
* **Labels:** Numerical labels (1, 2, 3, 4) and symbolic labels (x, B, A, λ) are used to identify specific points or components.
* **Transformation Arrow:** A blue double-headed arrow labeled "β" indicates the transformation process between the two configurations.
* **Dashed Ellipse:** A dashed ellipse encompasses a portion of the diagram on both sides, highlighting the region undergoing transformation.
### Detailed Analysis
**Left Configuration:**
* A node labeled "A" is located at the bottom-center. It has three vertical lines extending downwards, terminating in a triangular shape.
* A curved line labeled "x" enters the diagram from the bottom-left and connects to a node labeled "λ" at point "2".
* The node "λ" is connected to node "A" via a line labeled "1".
* The node "λ" is connected to another node (containing a three-pronged symbol) via a line.
* The node with the three-pronged symbol has an outgoing line labeled "3" pointing upwards.
* A line labeled "4" exits the node with the three-pronged symbol, pointing to the right and labeled "B".
* A dashed ellipse encompasses the node with the three-pronged symbol, the line connecting it to "λ", and the node "λ".
**Right Configuration:**
* A node labeled "A" is located at the bottom-center, identical to the left configuration.
* A curved line labeled "x" enters the diagram from the bottom-left and connects to a point labeled "2".
* The point labeled "2" is connected to a point labeled "1".
* The point labeled "1" is connected to node "A".
* A line rises upwards, bends to the left, and then curves back to the right, forming a loop. This line is labeled "3" at its top end.
* A line labeled "4" exits the loop, pointing to the right and labeled "B".
* A dashed ellipse encompasses the loop, the points labeled "1" and "2".
### Key Observations
* The transformation "β" rearranges the connections between the nodes and points, altering the spatial arrangement of the network.
* The dashed ellipse highlights the region where the most significant changes occur during the transformation.
* The node "A" and the lines extending from it remain unchanged during the transformation.
* The labels "x" and "B" remain consistent in both configurations, indicating they are external inputs/outputs.
### Interpretation
The diagram illustrates a specific type of network transformation, denoted by "β". This transformation involves rearranging the connections and spatial arrangement of nodes and edges within a defined region (indicated by the dashed ellipse). The transformation maintains certain elements (node "A", labels "x" and "B") while altering the connectivity of other elements (the loop and the nodes within the ellipse). This type of transformation could represent a simplification, optimization, or restructuring of the network for a specific purpose. The diagram provides a visual representation of the before-and-after states of the network, highlighting the changes induced by the "β" transformation.
</details>
This graph can be transformed into a graph of A [ x := B ] via (global FAN-OUT) and (CO-ASSOC) moves. The case when x is fresh for A is figured next.
<details>
<summary>Image 29 Details</summary>
### Visual Description
## Diagram: Beta Transformation
### Overview
The image depicts a diagram illustrating a transformation, labeled as "beta" (β), between two configurations of lines and nodes. The diagram shows how a structure with a lambda node (λ) and a three-pronged node transforms into a different configuration with a loop.
### Components/Axes
* **Nodes:** The diagram contains several nodes, including a node labeled "λ" (lambda) and a three-pronged node. There are also nodes labeled "A" and "B".
* **Lines:** Lines connect the nodes, with arrows indicating direction.
* **Labels:** Numerical labels (1, 2, 3, 4) are placed near the lines. The variable "x" is also present.
* **Transformation Label:** A blue double-headed arrow labeled "β" indicates the transformation between the two configurations.
* **Dashed Ellipse:** A dashed ellipse encloses a portion of the diagram on both sides of the transformation.
### Detailed Analysis
**Left Configuration:**
* A line originates from a point marked with a short perpendicular line and labeled "x". This line has an arrow pointing upwards and is labeled "2".
* The line connects to a node labeled "λ".
* Another line originates from node "A" and connects to the "λ" node. This line has an arrow pointing towards the "λ" node and is labeled "1".
* A line extends upwards from the "λ" node, with an arrow pointing upwards and connects to a three-pronged node.
* The three-pronged node has three lines connected to it. One line extends upwards and is labeled "3". Another line extends to the right and is labeled "4", terminating at node "B".
**Right Configuration:**
* A line originates from a point marked with a short perpendicular line and labeled "x". This line has an arrow pointing upwards and is labeled "2".
* A line originates from node "A" and curves upwards, eventually connecting to the line originating from "x". This line has an arrow pointing towards the connection point and is labeled "1".
* The line continues upwards, forming a loop, and then splits into two lines. One line extends upwards and is labeled "3". The other line extends to the right and is labeled "4", terminating at node "B".
**Transformation:**
* The transformation "β" converts the structure with the "λ" node and the three-pronged node into a structure with a loop.
### Key Observations
* The transformation "β" rearranges the connections between the nodes and lines.
* The dashed ellipse highlights the portion of the diagram that undergoes the most significant change during the transformation.
* The labels (1, 2, 3, 4, x, A, B) remain consistent across the transformation, indicating that these elements are preserved.
### Interpretation
The diagram illustrates a topological transformation, specifically a beta transformation, which alters the connectivity of a network of nodes and lines. The transformation involves replacing a structure containing a lambda node and a three-pronged node with a looped configuration. This type of transformation is often used in theoretical physics and mathematics to simplify or analyze complex systems. The diagram provides a visual representation of how the connections between the nodes are rearranged during the transformation, while preserving the identities of the key elements.
</details>
We see that the graph obtained by performing the graphic ( β ) move is the union of the graph of A and the graph of B with a gate added at the root. By pruning we are left with the graph of A , which is consistent to the fact that when x is fresh for A then ( λx.A ) B transforms by β reduction into A .
(e) In the next figure we see at the LHS the graph [ λx.Ax ] and at the RHS the graph [ A ].
<details>
<summary>Image 30 Details</summary>
### Visual Description
## Diagram: Transformation of a Lambda Expression
### Overview
The image depicts a diagram illustrating the transformation of a lambda expression. It shows a circular flow involving lambda abstraction and application, which is then transformed into a simpler form.
### Components/Axes
* **Nodes:**
* A node containing the Greek letter lambda (λ).
* A node containing a symbol resembling an upside-down "Y" inside a circle.
* A node labeled "A".
* **Arrows:** Arrows indicate the flow direction.
* **Transformation Arrow:** A blue, curved, double-headed arrow labeled "ext 1" indicates a transformation.
* **Final State:** A vertical arrow pointing upwards, with "A" below it, represents the final state after the transformation.
### Detailed Analysis
The diagram can be broken down into two main parts: the initial expression and the transformed expression.
1. **Initial Expression (Left Side):**
* A vertical arrow enters the lambda (λ) node from the top.
* An arrow exits the lambda node and leads to the upside-down "Y" node.
* An arrow exits the upside-down "Y" node and points to the "A" node.
* A curved arrow originates near the "A" node and loops back to the lambda (λ) node, completing the cycle.
* There is a red asterisk (*) on the left side of the loop.
2. **Transformation (Middle):**
* A blue, curved, double-headed arrow labeled "ext 1" points from the initial expression to the final state.
3. **Final State (Right Side):**
* A vertical arrow points upwards, with "A" below it.
### Key Observations
* The diagram illustrates a transformation process, likely a simplification or reduction of a lambda expression.
* The "ext 1" label suggests that this is one step in a larger series of transformations.
* The circular flow on the left side represents a recursive or self-referential process.
### Interpretation
The diagram likely represents a step in the evaluation or simplification of a lambda expression. The initial expression involves lambda abstraction and application, which is then transformed into a simpler form represented by "A". The "ext 1" transformation suggests that this is a single step in a larger process of expression reduction. The circular flow in the initial expression could represent a recursive function call or a self-referential definition. The red asterisk is likely a marker for a specific point of interest or a note for further analysis.
</details>
The red asterisk marks the arrow which appears in the construction [ λx.Ax ] from the variable x , taking into account the hypothesis x ∈ FV ( A ). We have a pattern where we can apply the ext1 move and we obtain [ A ], as claimed.
As an example, let us manipulate the graph of Ω = ( λx. ( xx ))( λx. ( xx )):
<details>
<summary>Image 31 Details</summary>
### Visual Description
## Diagram: Graph Reduction
### Overview
The image depicts a diagram illustrating a graph reduction process, likely in the context of computer science or formal systems. It shows two graph structures and transformations between them, labeled with "β" and "global FAN-OUT".
### Components/Axes
* **Nodes:** Represented as circles, some containing the symbol "λ" and others containing a "Y" shape.
* **Edges:** Represented as arrows, indicating the direction of flow or relationship between nodes.
* **Dashed Ellipses:** Highlight specific regions within the graphs, possibly indicating areas of focus for the transformation.
* **Labels:**
* "β": A label above a double-headed arrow, indicating a transformation.
* "global FAN-OUT": A label below a double-headed arrow, indicating another transformation.
### Detailed Analysis
**Left Graph Structure:**
* A top node with a "Y" shape inside. An arrow points upwards from this node.
* Two nodes below the top node, each containing "λ".
* Each "λ" node connects to a triangular structure consisting of three nodes, each containing a "Y" shape. These three nodes are connected in a cycle with arrows indicating the direction of the cycle.
* A dashed ellipse surrounds the top "Y" node and the left "λ" node.
**Right Graph Structure:**
* A top node with a "Y" shape inside. An arrow points upwards from this node.
* Two nodes below the top node, the top one with a "Y" shape inside, and the bottom one with "λ".
* A dashed ellipse surrounds the two top "Y" nodes.
* The "λ" node connects to a triangular structure consisting of three nodes, each containing a "Y" shape. These three nodes are connected in a cycle with arrows indicating the direction of the cycle.
**Transformations:**
* A double-headed arrow labeled "β" points from the left graph to the right graph, indicating a transformation process.
* A curved double-headed arrow labeled "global FAN-OUT" points from the right graph to the left graph, indicating another transformation process.
### Key Observations
* The "β" transformation appears to collapse the top portion of the left graph into a simpler structure in the right graph.
* The "global FAN-OUT" transformation seems to expand the simpler structure in the right graph back into the more complex structure in the left graph.
* The dashed ellipses highlight the parts of the graph that are most affected by the transformations.
### Interpretation
The diagram illustrates a graph reduction and expansion process, possibly related to lambda calculus or other formal systems. The "β" transformation likely represents a beta reduction, a fundamental operation in lambda calculus that simplifies expressions. The "global FAN-OUT" transformation may represent an inverse operation that expands or duplicates parts of the graph. The diagram suggests a cyclical relationship between these two transformations, where one can be used to simplify a graph and the other can be used to expand it back to its original form. The dashed ellipses highlight the regions of the graph that are most directly involved in these transformations.
</details>
We can pass from the LHS figure to the RHS figure by using a graphic ( β ) move. Conversely, we can pass from the RHS figure to the LHS figure by using a (global FAN-OUT) move. These manipulations correspond to the well known fact that Ω is left unchanged after β reduction: let U = λx. ( xx ), then Ω = UU = ( λx. ( xx )) U ↔ UU = Ω.
## 3.1 Example: combinatory logic
S , K and I combinators in GRAPH . The combinators I = λx.x , K = λx. ( λy. ( xy )) and S = λx. ( λy. ( λz. (( xz )( yz )))) have the following correspondents in GRAPH , denoted by the same letters:
<details>
<summary>Image 32 Details</summary>
### Visual Description
## Diagram: Combinatory Logic Diagrams
### Overview
The image presents three diagrams labeled I, K, and S, representing combinatory logic expressions. Each diagram consists of circles containing the symbol "λ" or a "Y" shape, connected by lines with arrows indicating the direction of flow. The diagrams illustrate the reduction rules for the I, K, and S combinators.
### Components/Axes
* **Nodes:** Circles containing either "λ" or a "Y" shape.
* **Edges:** Lines connecting the nodes, with arrows indicating the direction of flow.
* **Labels:** "I", "K", and "S" are located below each diagram.
* **Input/Output:** Each diagram has a single input at the top and outputs indicated by arrows.
### Detailed Analysis
**Diagram I:**
* A circle containing "λ" is connected to itself by a loop with an arrow.
* An input arrow points towards the circle from the top.
* An output arrow emerges from the circle, pointing upwards.
**Diagram K:**
* Two circles, each containing "λ", are connected by an arrow pointing from the left circle to the right circle.
* A line with a short perpendicular line segment (representing deletion) points downwards from the right circle.
* A curved arrow connects the right circle back to the left circle.
* An input arrow points towards the left circle from the top.
* An output arrow emerges from the left circle, pointing upwards.
**Diagram S:**
* Three circles containing "λ" are arranged horizontally, connected by arrows pointing from left to right.
* The rightmost circle containing "λ" has a line extending downwards, leading to a tree-like structure composed of four "Y" shaped nodes.
* The "Y" nodes are connected by arrows, forming a binary tree structure.
* Arrows connect the leftmost and middle "λ" circles to the bottom "Y" node.
* An input arrow points towards the leftmost circle from the top.
* An output arrow emerges from the top-left "λ" circle, pointing upwards.
### Key Observations
* The diagrams visually represent the reduction rules of the I, K, and S combinators.
* The "λ" nodes likely represent lambda abstractions.
* The "Y" nodes likely represent application.
* The arrows indicate the flow of data or computation.
### Interpretation
The diagrams illustrate the fundamental combinators I, K, and S, which are essential components of combinatory logic. Combinatory logic is a notation for expressing mathematical logic without using variable names. The diagrams provide a visual representation of how these combinators transform expressions. The I combinator represents identity, the K combinator represents a constant function, and the S combinator represents substitution. The tree-like structure in the S combinator diagram suggests a more complex transformation involving multiple applications. These diagrams are useful for understanding the underlying mechanisms of functional programming and lambda calculus.
</details>
Proposition 3.2 (a) By one graphic ( β ) move I A transforms into A , for any A ∈ GRAPH with one output.
(b) By two graphic ( β ) moves, followed by a global pruning, for any A,B ∈ GRAPH with one output, the graph ( K A ) B transforms into A .
(c) By five graphic ( β ) moves, followed by one local pruning move, the graph ( S K ) K transforms into I .
(d) By three graphic ( β ) moves followed by a (global FAN-OUT) move, for any A,B,C ∈ GRAPH with one output, the graph (( S A ) B ) C transforms into the graph ( A C ) ( B C ) .
Proof. The proof of (b) is given in the next figure.
<details>
<summary>Image 33 Details</summary>
### Visual Description
## Diagram: Lambda Calculus Reduction
### Overview
The image depicts a series of transformations in lambda calculus, showing the reduction steps from a complex expression to a simplified form. The transformations are labeled with "β" and "global pruning".
### Components/Axes
* **Nodes:** Represented by circles containing either a "λ" symbol or a symbol resembling a "Y" with a circle around it.
* **Edges:** Represented by arrows, indicating the flow of data or function application.
* **Labels:** "A" and "B" are used as labels for the edges.
* **Reduction Steps:** Indicated by blue double-headed arrows labeled "β" and "global pruning".
* **Dashed Ovals:** Enclose parts of the diagram to highlight the sections being transformed.
### Detailed Analysis
**Leftmost Diagram:**
* A node with the "Y" symbol at the top, with an outgoing edge labeled "B".
* Below it, a node with the "Y" symbol, with an outgoing edge labeled "A".
* Below that, two nodes with the "λ" symbol. The rightmost "λ" node has a downward pointing edge with a small horizontal line at the end.
* An edge connects the bottom "λ" node to the "Y" node above it.
* A curved edge connects the rightmost "λ" node to the leftmost "λ" node.
* A dashed oval encloses the top two "Y" nodes and the leftmost "λ" node.
**Middle Diagram:**
* A node with the "Y" symbol at the top, with an outgoing edge labeled "B".
* Below it, a node with the "λ" symbol, with an outgoing edge labeled "A".
* A downward pointing edge with a small horizontal line at the end.
* A dashed oval encloses both nodes.
**Rightmost Diagram:**
* A vertical edge labeled "A" pointing upwards.
* A curved edge labeled "B" pointing downwards, then curving back up to itself.
* A vertical edge pointing downwards, labeled "global pruning".
* The letter "A" below the "global pruning" arrow.
**Transformations:**
* The transformation from the leftmost diagram to the middle diagram is labeled "β".
* The transformation from the middle diagram to the rightmost diagram is labeled "β".
* The transformation from the rightmost diagram to the final "A" is labeled "global pruning".
### Key Observations
* The diagram illustrates the process of simplifying a lambda calculus expression through beta reduction and global pruning.
* The dashed ovals highlight the parts of the expression that are being transformed in each step.
* The labels "A" and "B" likely represent variables or expressions being passed between the nodes.
### Interpretation
The diagram demonstrates the step-by-step reduction of a lambda calculus expression. The initial complex expression is simplified through beta reduction (β), which involves substituting variables with their corresponding values. The final step, "global pruning," removes unnecessary or redundant parts of the expression, resulting in a simplified form represented by "A". The diagram provides a visual representation of the process of evaluating a lambda expression, showing how it is transformed from a complex structure to a simpler, equivalent form.
</details>
The proof of (c) is given in the following figure.
(a) and (d) are left to the interested reader.
<details>
<summary>Image 34 Details</summary>
### Visual Description
## Diagram: Lambda Calculus Reduction
### Overview
The image depicts a series of diagrams illustrating the reduction steps in lambda calculus. The diagrams use a graphical notation to represent lambda terms and their transformations through beta reduction and local pruning. The transformations are shown through a sequence of steps, with arrows indicating the direction of the reduction.
### Components/Axes
* **Nodes:** Represented by circles, some containing the symbol "λ" (lambda).
* **Edges:** Represented by lines with arrows, indicating the flow of data or application.
* **Labels:**
* "K": Appears next to some nodes.
* "λ": Appears inside some nodes.
* "twice β": Indicates two beta reduction steps.
* "β": Indicates a single beta reduction step.
* "local pruning": Indicates a local pruning step.
### Detailed Analysis
The diagram can be broken down into three horizontal sections, each showing a transformation:
1. **Top Section:**
* Starts with a complex structure at the top-left, containing nodes labeled "K" and "λ".
* The structure is transformed "twice β" into a more complex structure on the top-right, containing multiple "λ" nodes and loops.
2. **Middle Section:**
* The structure on the top-right is transformed "twice β" downwards into a simpler structure on the bottom-right.
3. **Bottom Section:**
* Starts with a simple loop containing a "λ" node on the bottom-left.
* This loop undergoes "local pruning" to become a structure with two "λ" nodes and one unlabeled node in the center.
* This structure then undergoes a "β" reduction to become a structure with four "λ" nodes and one unlabeled node in the center.
**Specific Transformations:**
* **Top-Left to Top-Right:** A complex structure with "K" nodes is reduced twice using beta reduction to a structure with multiple lambda abstractions and loops.
* **Top-Right to Bottom-Right:** The complex structure is further reduced twice using beta reduction to a simpler structure with a single input and a loop.
* **Bottom-Left to Bottom-Middle:** A simple lambda abstraction loop is pruned locally, resulting in a structure with two lambda abstractions and a central node.
* **Bottom-Middle to Bottom-Right:** The pruned structure undergoes a beta reduction, resulting in a structure with four lambda abstractions and a central node.
### Key Observations
* The diagram illustrates the simplification of lambda terms through beta reduction and local pruning.
* The transformations show how complex structures can be reduced to simpler forms.
* The use of graphical notation provides a visual representation of the reduction process.
### Interpretation
The diagram demonstrates the process of simplifying lambda calculus expressions through a series of reduction steps. The transformations highlight how complex lambda terms can be reduced to simpler, equivalent forms using beta reduction and local pruning. The graphical notation provides a visual aid for understanding the reduction process, making it easier to follow the transformations and understand the underlying concepts of lambda calculus. The diagram showcases the power of lambda calculus in representing and manipulating computations.
</details>
## 4 Using graphic lambda calculus
The manipulations of graphs presented in this section can be applied for graphs which represent lambda terms. However, they can also be applied for graphs which do not represent lambda terms.
Fixed points. Let's start with a graph A ∈ GRAPH , which has one distinguished input and one distinguished output.I represent this as follows.
$$\rightarrow A \rightarrow$$
For any graph B with one output, we denote by A ( B ) the graph obtained by grafting the output of B to the input of A .
I want to find B such that A ( B ) ↔ B , where ↔ means any finite sequence of moves in graphic lambda calculus. I call such a graph B a fixed point of A .
The solution of this problem is the same as in usual lambda calculus. We start from the following succession of moves:
<details>
<summary>Image 35 Details</summary>
### Visual Description
## Diagram: Global Fan-Out and Beta Reduction
### Overview
The image presents a diagram illustrating transformations between different configurations of a network or graph. It shows a "Global Fan-Out" transformation between two network structures and a "Beta Reduction" transformation to a simplified structure. The diagram uses nodes, edges with arrows indicating direction, and annotations to represent these transformations.
### Components/Axes
* **Nodes:** Represented by circles and a "Y" shaped symbol. Some circles contain the symbol "λ".
* **Edges:** Represented by lines with arrows, indicating the direction of flow or connection.
* **Annotations:**
* "A": Appears near circular loops.
* "λ": Appears inside some circular nodes.
* "GLOBAL": Blue text above a double-headed arrow.
* "FAN-OUT": Blue text below a double-headed arrow.
* "β": Blue text near a curved arrow.
* **Green Dashed Ovals:** Enclose specific regions of the network to highlight parts of the transformation.
### Detailed Analysis or ### Content Details
**Left Structure:**
* A vertical chain of nodes.
* Top node: A circle containing "λ" with a loop labeled "A" above it. An arrow points from the loop to the node. An arrow points down from the node.
* Middle section: Two "Y" shaped nodes stacked vertically, enclosed by a green dashed oval. Arrows point from the top node to the top "Y" node, and from the top "Y" node to the bottom "Y" node.
* Bottom: An arrow points down from the bottom "Y" node.
**Right Structure (Top):**
* Two separate structures connected.
* Left structure: A circle containing "λ" with a loop labeled "A" above it. An arrow points from the loop to the node.
* Right structure: A circle containing "λ" with a loop labeled "A" above it. An arrow points from the loop to the node. An arrow points down from the node.
* The two structures are connected by an arrow from the left structure to a "Y" shaped node. The "Y" shaped node is connected to the right structure. The "Y" shaped node and the right structure's "λ" node are enclosed by a green dashed oval.
* An arrow points down from the "Y" shaped node.
**Bottom Structure:**
* A vertical chain of nodes.
* Top node: A circle containing "λ" with a loop labeled "A" above it. An arrow points from the loop to the node. An arrow points down from the node.
* Bottom: An arrow labeled "A" points down from the node.
**Transformations:**
* **GLOBAL FAN-OUT:** A double-headed arrow between the left and right structures, labeled "GLOBAL" above and "FAN-OUT" below.
* **β Reduction:** A curved arrow from the right structure to the bottom structure, labeled "β".
### Key Observations
* The "GLOBAL FAN-OUT" transformation rearranges the network structure, duplicating a portion of the graph.
* The "β Reduction" transformation simplifies the network structure.
* The green dashed ovals highlight the parts of the network that are being transformed.
### Interpretation
The diagram illustrates two fundamental transformations in a network or graph. The "GLOBAL FAN-OUT" transformation represents a duplication or branching of a part of the network, potentially increasing its complexity or redundancy. The "β Reduction" transformation represents a simplification or reduction of the network, potentially optimizing its performance or reducing its complexity. The "β Reduction" is applied after the "GLOBAL FAN-OUT". The diagram suggests a process of network manipulation involving both expansion and simplification steps. The "λ" symbol likely represents a specific type of node or function within the network, and the "A" label likely represents a specific type of connection or attribute.
</details>
This is very close to the solution, we only need a small modification:
<details>
<summary>Image 36 Details</summary>
### Visual Description
## Diagram: Global Fan-Out Transformation
### Overview
The image depicts a diagram illustrating a transformation process, likely in the context of computer science or mathematics. It shows an initial state, a transformation step labeled "GLOBAL FAN-OUT," and the resulting state. A further transformation step labeled "β" is also shown. The diagram uses nodes, edges, and specific symbols (lambda, fan-out) to represent the transformation.
### Components/Axes
* **Nodes:** Represented by circles, some containing the lambda symbol (λ) and others containing a fan-out symbol.
* **Edges:** Represented by arrows, indicating the flow or relationship between nodes.
* **Labels:**
* "A": Appears near certain edges, possibly indicating a variable or parameter.
* "GLOBAL FAN-OUT": Describes the transformation between the first two diagrams.
* "β": Describes the transformation between the second and third diagrams.
* **Green Dashed Ovals:** Highlight specific regions in the first two diagrams, possibly indicating the area affected by the "GLOBAL FAN-OUT" transformation.
### Detailed Analysis
**Diagram 1 (Left):**
* A node labeled "λ" at the top, with an incoming edge labeled "A" forming a loop with two fan-out nodes.
* A vertical chain of nodes below the "λ" node, consisting of a green dashed oval containing two fan-out nodes, followed by another fan-out node.
* A downward-pointing arrow at the bottom.
**Transformation: GLOBAL FAN-OUT**
* A blue double-headed arrow labeled "GLOBAL FAN-OUT" indicates the transformation from the first diagram to the second.
**Diagram 2 (Top Right):**
* A node labeled "λ" at the top, with an incoming edge labeled "A" forming a loop with two fan-out nodes.
* A vertical chain of nodes below the "λ" node, consisting of a green dashed oval containing two fan-out nodes, followed by a downward-pointing arrow.
* The loop containing "A" and the fan-out nodes is now connected to the vertical chain.
**Transformation: β**
* A blue curved arrow labeled "β" indicates the transformation from the second diagram to the third.
**Diagram 3 (Bottom):**
* A node labeled "λ" at the top, with an incoming edge labeled "A" forming a loop with two fan-out nodes.
* A vertical chain of nodes below the "λ" node, consisting of two fan-out nodes, followed by another fan-out node.
* A downward-pointing arrow at the bottom, labeled "A".
### Key Observations
* The "GLOBAL FAN-OUT" transformation appears to involve rearranging the connections between the loop containing "A" and the vertical chain of nodes.
* The "β" transformation seems to simplify or reduce the structure of the diagram.
* The green dashed ovals highlight the region where the "GLOBAL FAN-OUT" transformation occurs.
### Interpretation
The diagram illustrates a sequence of transformations applied to a graph-like structure. The "GLOBAL FAN-OUT" transformation likely represents a specific operation that rearranges connections within the graph. The "β" transformation suggests a simplification or reduction step, possibly related to beta reduction in lambda calculus. The diagram provides a visual representation of how these transformations alter the structure of the graph, potentially representing a computation or algorithm. The "A" labels might represent variables or parameters passed between nodes. The fan-out nodes likely represent duplication or branching of data flow.
</details>
Grafting, application or abstraction? If the A , B from the previous paragraph were representing lambda terms, then the natural operation between them is not grafting, but the application. Or, in graphic lambda calculus the application it's represented by an elementary graph, therefore AB (seen as the term in lambda calculus which is obtained as the application of A to B ) is not represented as a grafting of the output of B to the input of A .
We can easily transform grafting into the application operation.
<details>
<summary>Image 37 Details</summary>
### Visual Description
## Diagram: Beta Reduction
### Overview
The image illustrates a beta reduction process using a diagrammatic notation. It shows the transformation of one expression into another through a series of steps, represented by arrows and symbols.
### Components/Axes
* **Arrows:** Indicate the direction of flow or transformation.
* **Symbols:** Represent different operations or elements within the expression.
* **Labels:** "A" and "B" are used as labels.
* **Equality Sign:** Three horizontal lines indicate equality.
* **Beta Symbol (β):** A blue beta symbol with a double-headed arrow indicates the beta reduction step.
* **Lambda Symbol (λ):** A lambda symbol is present in a circle.
* **Inverted "V" Symbol:** An inverted "V" symbol is present in a circle.
### Detailed Analysis
The diagram can be broken down into three distinct sections:
1. **Left Side:**
* Two vertical arrows pointing upwards.
* The label "A" is placed between the arrows.
* The label "B" is placed below the second arrow.
2. **Middle Section:**
* An equality sign (three horizontal lines).
* A loop with an arrow pointing from the top to the right, then curving back to the top.
* The label "A" is placed inside the loop.
* An arrow pointing to the right, labeled "B".
3. **Right Side:**
* A blue double-headed arrow labeled "β" above it, indicating a beta reduction.
* A tree-like structure with nodes and branches.
* The top node contains an inverted "V" symbol.
* The left branch leads to a node containing a lambda symbol (λ).
* The left branch loops back to a node labeled "A".
* The right branch leads to a node labeled "B".
* All arrows point upwards, except for the loop on the left side.
### Key Observations
* The diagram shows a transformation from a linear structure to a tree-like structure.
* The beta reduction step involves replacing a lambda expression with its equivalent form.
* The labels "A" and "B" represent variables or expressions.
### Interpretation
The diagram illustrates a beta reduction process, a fundamental concept in lambda calculus and functional programming. It shows how an expression containing a lambda abstraction can be simplified by substituting the argument into the body of the abstraction. The transformation from the left side to the right side represents the application of the beta reduction rule. The beta symbol (β) above the double-headed arrow explicitly denotes this reduction step. The diagram provides a visual representation of this process, making it easier to understand the underlying concept.
</details>
Suppose that A and B are graphs representing lambda terms, more precisely suppose that A is representing a term (denoted by A too) and it's input represents a free variable x of the term A . Then the grafting of B to A is the term A [ x := B ] and the graph from the right is representing ( λx.A ) B , therefore both graphs are representing terms from lambda calculus.
We can transform grafting into something else:
<details>
<summary>Image 38 Details</summary>
### Visual Description
## Diagram: String Diagram Transformation
### Overview
The image depicts a transformation of a string diagram. It shows an equivalence between a simple vertical stack of strings labeled A and B, and a more complex diagram involving loops and nodes labeled with λ. The transformation is mediated by a beta (β) reduction.
### Components/Axes
* **Strings:** Represented by vertical lines with arrows indicating direction.
* **Labels:** A, B, and λ are used to label strings and nodes.
* **Nodes:** Represented by circles, some containing the symbol λ.
* **Arrows:** Indicate the direction of flow along the strings.
* **Equivalence Symbol:** Three horizontal lines indicating equivalence.
* **Transformation Symbol:** A blue double-headed arrow labeled with β above it.
### Detailed Analysis
The diagram can be broken down into three main sections:
1. **Left Diagram:**
* Two vertical strings, one above the other.
* The top string is labeled "A".
* The bottom string is labeled "B".
* Both strings have upward-pointing arrows.
2. **Middle Section:**
* An equivalence symbol (≡).
* A diagram with a single vertical string labeled "B" at the bottom, with an upward-pointing arrow.
* The string splits into a loop labeled "A" with an upward-pointing arrow, and then rejoins the original string.
3. **Right Diagram:**
* A blue double-headed arrow labeled "β" above it, indicating a transformation.
* A diagram with a string labeled "B" on the left, pointing towards a node containing "λ".
* A string exits the top of the "λ" node with an upward-pointing arrow.
* Another string exits the "λ" node and connects to another node containing "¬λ".
* A loop labeled "A" with an upward-pointing arrow emerges from the "¬λ" node.
### Key Observations
* The transformation involves replacing a simple stack of strings with a more complex network of nodes and loops.
* The "β" symbol suggests a beta reduction, a common operation in lambda calculus and related formalisms.
* The presence of "λ" and "¬λ" nodes suggests a connection to lambda calculus or a similar system of logic.
* The arrows indicate the direction of flow, which is important for understanding the meaning of the diagram.
### Interpretation
The diagram illustrates a transformation rule within a string diagram calculus. The "β" reduction transforms a simple composition of strings into a more complex structure involving lambda abstractions and applications. This type of transformation is common in areas like quantum computation, category theory, and programming language semantics, where string diagrams are used to represent computations and logical operations. The diagram suggests that the simple stack of strings "A" and "B" is equivalent to a more complex expression involving lambda abstractions and applications, as represented by the nodes and loops on the right-hand side. The diagram is a visual representation of a formal rule for manipulating string diagrams.
</details>
This has no meaning in lambda calculus, but excepting the orientation of one of the arrows of the graph from the right, it looks like if the abstraction gate (the λ gate) plays the role of an application operation.
Zippers and combinators as half-zippers. Let's take n ≥ 1 a natural number and let's consider the following graph in GRAPH , called the n-zipper:
<details>
<summary>Image 39 Details</summary>
### Visual Description
## Diagram: Tensor Network Equivalence
### Overview
The image presents a diagram illustrating the equivalence between two tensor network representations. On the left, a network of tensors connected in a chain-like structure is shown. On the right, a more compact representation of the same network is depicted. The diagram uses symbols to represent tensors and lines to represent tensor contractions.
### Components/Axes
**Left Diagram:**
* **Tensors:** Represented by circles containing the symbol "λ".
* **Input Tensors:** Labeled as A1, A2, ... , An, and B, each with an arrow pointing towards the tensor network.
* **Output Tensors:** Labeled as A'1, A'2, ... , A'n, and B', each with an arrow pointing away from the tensor network.
* **Ellipsis:** Represented by dotted lines, indicating that the pattern continues.
**Right Diagram:**
* **Box:** A rectangular box represents the entire tensor network.
* **Input Tensors:** Labeled as A1, A2, ... , An, and B, each with an arrow pointing towards the box.
* **Output Tensors:** Labeled as A'1, A'2, ... , A'n, and B', each with an arrow pointing away from the box.
* **Ellipsis:** Represented by dotted lines within the box, indicating that the pattern continues.
* **Internal Lines:** Zig-zag lines within the box connect the input and output tensors.
**Equivalence Symbol:**
* The symbol "≡" is placed between the two diagrams, indicating that they are equivalent representations.
### Detailed Analysis
**Left Diagram:**
* The tensor network consists of 'n' tensors connected in a chain.
* Each tensor has one input tensor (A1, A2, ..., An) and one output tensor (A'1, A'2, ..., A'n).
* The input tensor B is connected to the first tensor in the chain.
* The output tensor B' is connected to the last tensor in the chain.
**Right Diagram:**
* The box represents the entire tensor network as a single unit.
* The input and output tensors are connected to the box.
* The zig-zag lines within the box represent the tensor contractions that occur within the network.
### Key Observations
* The diagram illustrates that a complex tensor network can be represented by a simpler, more compact diagram.
* The equivalence symbol indicates that the two representations are mathematically equivalent.
* The ellipsis indicates that the pattern can be extended to any number of tensors.
### Interpretation
The diagram demonstrates the concept of tensor network equivalence, which is a fundamental concept in tensor network theory. It shows that a complex tensor network can be represented by a simpler, more compact diagram without losing any information. This is useful for simplifying calculations and visualizing complex tensor networks. The diagram highlights the relationship between the individual tensors in the network and the overall network structure. The use of ellipsis indicates that the concept can be generalized to tensor networks of arbitrary size.
</details>
At the left is the n-zipper graph; at the right is a notation for it, or a 'macro'. The zipper graph is interesting because it allows to perform (nontrivial) graphic beta moves in a fixed order. In the following picture is figured in red the place where the first graphic beta move is applied.
<details>
<summary>Image 40 Details</summary>
### Visual Description
## Diagram: Diagram of a Transformation
### Overview
The image shows a diagram illustrating a transformation between two configurations of interconnected nodes and lines. The diagram consists of two main parts, one on the left and one on the right, connected by a double-headed arrow indicating a transformation or equivalence. Each part shows a network of nodes labeled with 'A' and 'B' variants, connected by lines with arrows indicating direction.
### Components/Axes
* **Nodes:** Represented by circles, some containing the symbol 'λ'.
* **Lines:** Represent connections between nodes, with arrows indicating direction.
* **Labels:** 'A1', 'A2', 'An', 'A1*', 'A1'', 'A2'', 'An'', 'B', 'B'' are used to label the nodes.
* **Double-Headed Arrow:** Located in the center, indicating a transformation or equivalence between the left and right configurations.
### Detailed Analysis
**Left Configuration:**
* A node labeled 'B' is at the bottom.
* A series of nodes labeled 'An', 'A2', and 'A1' are connected vertically, moving upwards from 'B'. Each node has an arrow pointing upwards.
* The node labeled 'A1' is highlighted with a red circle.
* From 'A1', two arrows extend horizontally to the right, connecting to a node labeled 'A1*'.
* Above 'A1', there is a series of nodes labeled 'A2'' and 'An'', leading to a node labeled 'B'' at the top.
**Right Configuration:**
* A node labeled 'B' is at the bottom.
* A series of nodes labeled 'An', 'A2' are connected vertically, moving upwards from 'B'. Each node has an arrow pointing upwards.
* At the top of the vertical series, there is a central node.
* From the central node, two arrows extend horizontally to the right and left, connecting to nodes labeled 'A2'' and 'A2'.
* Above the central node, there is a series of nodes labeled 'An'', leading to a node labeled 'B'' at the top.
* A curved arrow connects 'A1' to 'A1*'.
### Key Observations
* The transformation involves rearranging the connections between the nodes.
* The 'A1' node and its connection to 'A1*' are highlighted in the left configuration.
* The right configuration shows a more symmetrical arrangement of nodes.
### Interpretation
The diagram illustrates a transformation or equivalence between two different network configurations. The transformation appears to involve rearranging the connections around the 'A1' node, which is highlighted in the left configuration. The double-headed arrow suggests that the two configurations are equivalent in some sense, possibly representing different ways of representing the same underlying system or process. The use of 'λ' within some nodes might indicate a specific type of operation or function associated with those nodes. The diagram likely represents a step in a larger process or a simplification of a more complex system.
</details>
In terms of zipper notation this graphic beta move has the following appearance:
<details>
<summary>Image 41 Details</summary>
### Visual Description
## Diagram: Network Transformation
### Overview
The image presents a diagram illustrating a network transformation or equivalence. It shows two different configurations of interconnected components, with an arrow indicating their interconvertibility. The diagram appears to represent a system where inputs are processed and outputs are generated, with a transformation occurring between two different arrangements of these components.
### Components/Axes
* **Components:** The diagram features rectangular blocks, each with internal lines suggesting a processing or routing function. These blocks are labeled with "A" and "B" variants, with numerical subscripts for the "A" variants.
* **Arrows:** Arrows indicate the direction of flow or interaction between the components.
* **Labels:** The labels include:
* A₁, A'₁
* A₂, A'₂
* Aₙ, A'ₙ
* B, B'
* **Symbol:** A double-headed arrow in the center indicates a transformation or equivalence between the two configurations.
### Detailed Analysis
The diagram can be divided into two main configurations, left and right, connected by a transformation arrow.
**Left Configuration:**
* A series of blocks labeled A₁, A₂, ..., Aₙ are stacked vertically.
* Each A block has an input arrow on the left (A₁, A₂, Aₙ) and an output arrow on the right (A'₁, A'₂, A'ₙ).
* The bottom block is labeled "B" and has an upward-pointing output arrow.
**Right Configuration:**
* A series of blocks labeled A₂, ..., Aₙ are stacked vertically.
* Each A block has an input arrow on the left (A₂, Aₙ) and an output arrow on the right (A'₂, A'ₙ).
* The top block is labeled "B'" and has an upward-pointing output arrow.
* The bottom of the diagram has an input labeled A₁ and an output labeled A'₁.
**Transformation:**
* A double-headed arrow connects the two configurations, indicating that they are equivalent or can be transformed into each other.
### Key Observations
* The transformation appears to involve rearranging the order or connections of the components.
* The "A" components seem to be processed sequentially in the left configuration, while in the right configuration, A₁ is separated from the rest.
* The "B" component changes its position and label (B to B') during the transformation.
### Interpretation
The diagram likely represents a network or system where the order of processing or connections between components can be rearranged without changing the overall functionality. The transformation suggests that the system is invariant under certain rearrangements. The separation of A₁ in the right configuration might indicate a specific optimization or simplification that can be achieved through this transformation. The diagram could be used to illustrate concepts in network theory, signal processing, or other fields where interconnected components are used to perform a specific task.
</details>
We see that a n-zipper transforms into a (n-1)-zipper plus an arrow. We may repeat this move, as long as we can. This procedure defines a 'zipper move':
<details>
<summary>Image 42 Details</summary>
### Visual Description
## Diagram: ZIPn Transformation
### Overview
The image presents a diagram illustrating a transformation labeled "ZIPn". It shows a series of stacked rectangular blocks on the left, transforming into a series of curved lines on the right. Arrows indicate the direction of flow or transformation.
### Components/Axes
* **Left Side:**
* A vertical stack of rectangular blocks.
* Each block has inputs labeled A₁, A₂, ... Aₙ on the left side.
* Each block has outputs labeled A'₁, A'₂, ... A'ₙ on the right side.
* The bottom block has an input labeled B.
* The top block has an output labeled B'.
* Ellipsis (...) indicate continuation of the pattern.
* **Center:**
* The label "ZIPn" with a double-headed arrow indicating a reversible transformation.
* **Right Side:**
* A series of curved lines, each corresponding to an Aᵢ input/output pair.
* Inputs labeled A₁, A₂, ... Aₙ on the left side.
* Outputs labeled A'₁, A'₂, ... A'ₙ on the right side.
* Arrows on the curved lines indicate direction from Aᵢ to A'ᵢ.
* An input labeled B, connected to an output labeled B' via a curved line with an upward-pointing arrow.
* Ellipsis (...) indicate continuation of the pattern.
### Detailed Analysis
* **Left Side:** The stacked blocks suggest a sequential process or a series of identical operations. The inputs Aᵢ and output A'ᵢ are associated with each block.
* **Center:** The "ZIPn" label indicates the name of the transformation. The double-headed arrow suggests that the transformation is reversible.
* **Right Side:** The curved lines represent the transformed state of the inputs Aᵢ. The arrow directions indicate the flow from input to output. The B to B' transformation is separate from the Aᵢ transformations.
### Key Observations
* The transformation "ZIPn" appears to relate a stacked, block-based representation to a series of curved lines.
* The Aᵢ inputs and outputs are transformed individually.
* The B input and B' output are transformed separately from the Aᵢ inputs and outputs.
### Interpretation
The diagram illustrates a transformation, "ZIPn", that converts a series of stacked blocks into a series of curved lines. The transformation appears to act on each Aᵢ input independently, while also transforming a separate input B. The reversible nature of the transformation suggests that it is possible to convert between the stacked block representation and the curved line representation. The diagram could represent a mathematical operation, a data processing algorithm, or a physical process.
</details>
We may see the 1-zipper move as the graphic beta move, which transforms the 1-zipper into two arrows.
The combinator I = λx.x satisfies the relation IA = A . In the next figure it is shown that I (figured in green), when applied to A , is just a half of the 1-zipper, with an arrow added (figured in blue).
<details>
<summary>Image 43 Details</summary>
### Visual Description
## Diagram: Diagram of Equivalent Representations
### Overview
The image presents a diagram illustrating the equivalence between two different graphical representations. The diagram consists of two distinct arrangements of symbols and lines, connected by a triple horizontal line symbol, indicating equivalence. The left side features a green loop connected to a green circle containing the symbol "λ", which is connected to a black circle containing a "Y" symbol. The right side features a blue loop connected to a square containing two diagonal lines. Arrows indicate the direction of flow or connection.
### Components/Axes
* **Left Side:**
* Green Loop: A curved line forming a loop, colored green.
* Green Circle: A circle colored green, containing the symbol "λ".
* Black Circle: A circle colored black, containing the symbol "Y".
* Arrows: Indicate direction of flow or connection.
* "A": A label positioned to the right of the rightmost black circle.
* **Equivalence Symbol:**
* Triple Horizontal Lines: Three horizontal lines stacked on top of each other, indicating equivalence.
* **Right Side:**
* Blue Loop: A curved line forming a loop, colored blue.
* Square: A square containing two diagonal lines.
* Arrows: Indicate direction of flow or connection.
* "A": A label positioned to the right of the square.
### Detailed Analysis
* **Left Side:**
* A green loop starts from the bottom of the green circle containing "λ" and curves back to connect to the left side of the same circle.
* The green circle containing "λ" is connected to the black circle containing "Y" via a horizontal line.
* The black circle containing "Y" has an arrow pointing upwards and another arrow pointing to the left, connecting to the green circle.
* The label "A" is positioned to the right of the black circle.
* **Equivalence Symbol:**
* The triple horizontal lines are positioned between the left and right sides of the diagram, indicating equivalence.
* **Right Side:**
* A blue loop starts from the bottom of the square and curves back to connect to the left side of the square.
* The square contains two diagonal lines.
* The square has an arrow pointing upwards and another arrow pointing to the right.
* The label "A" is positioned to the right of the square.
### Key Observations
* The diagram illustrates the equivalence between two different graphical representations.
* The left side features a green loop connected to a green circle containing "λ", which is connected to a black circle containing "Y".
* The right side features a blue loop connected to a square containing two diagonal lines.
* Arrows indicate the direction of flow or connection.
### Interpretation
The diagram likely represents an equivalence in a mathematical or physical system. The symbols "λ" and "Y", along with the loops and arrows, suggest a flow or transformation process. The equivalence symbol indicates that the two different arrangements of symbols and lines represent the same underlying concept or operation. The labels "A" on both sides might represent a common input or output. The diagram could be used to simplify or transform a complex system into a more manageable form.
</details>
By opening the zipper we obtain A , as it should.
The combinator K = λxy.x satisfies KAB = ( KA ) B = A . In the next figure the combinator K (in green) appears as half of the 2-zipper, with one arrow and one termination gate added (in blue).
<details>
<summary>Image 44 Details</summary>
### Visual Description
## Diagram: Equivalent Representations of a System
### Overview
The image presents two equivalent representations of a system, likely related to control systems or signal processing. The left side shows a block diagram with a specific configuration, while the right side shows an equivalent representation using a different set of components. The two sides are linked by an "equals" sign, indicating equivalence.
### Components/Axes
* **Left Side:**
* A rectangular block with internal diagonal lines.
* Input arrows pointing into the block from the left and bottom.
* Output arrows pointing out of the block to the top and right, labeled "B" and "A" respectively.
* A feedback loop in blue connecting the output "A" to the bottom input.
* A short horizontal line segment on the left, connected to the input arrow.
* **Right Side:**
* Two circular nodes, each containing the symbol "λ" (lambda), colored green.
* Two circular nodes, each containing the symbol "∧" (logical AND), colored black.
* Input arrows pointing into the top "∧" node and the rightmost "∧" node, labeled "B" and "A" respectively.
* A feedback loop in green connecting the bottom "λ" node to the leftmost "λ" node.
* Arrows indicating the flow of signals between the nodes.
* A short horizontal line segment on the left, connected to the green feedback loop.
* **Central Connector:**
* An equals sign "===" between the two diagrams, indicating equivalence.
### Detailed Analysis or Content Details
**Left Side (Block Diagram):**
* The rectangular block has two inputs and two outputs.
* The input from the left goes into the top of the block.
* The input from the bottom is the feedback from output A.
* The output at the top is labeled B.
* The output on the right is labeled A.
* The feedback loop connects output A to the bottom input of the block.
**Right Side (Equivalent Representation):**
* The top "∧" node has an input labeled "B".
* The rightmost "∧" node has an input labeled "A".
* The two "∧" nodes are connected by an arrow.
* The leftmost "λ" node is connected to the top "∧" node.
* The bottom "λ" node is connected to the rightmost "λ" node.
* The feedback loop connects the bottom "λ" node to the leftmost "λ" node.
### Key Observations
* The two diagrams represent the same system using different notations.
* The left side uses a block diagram approach, while the right side uses a node-based representation.
* The "λ" nodes likely represent some form of gain or scaling, while the "∧" nodes likely represent logical AND operations.
* The feedback loop is present in both diagrams, indicating a closed-loop system.
### Interpretation
The image demonstrates the equivalence between two different representations of a system. The block diagram on the left provides a high-level view of the system, while the node-based representation on the right provides a more detailed view of the internal components and their interactions. The use of "λ" and "∧" symbols suggests that the system may involve both linear and non-linear operations. The feedback loop indicates that the system is likely designed to regulate or control some variable. The equivalence of the two diagrams implies that they can be used interchangeably to analyze or design the system.
</details>
After opening the zipper we obtain a pair made by A and B which gets the termination gate on top of it. A global pruning move sends B to the trash bin.
Finally, the combinator S = λxyz. (( xz )( yz )) satisfies SABC = (( SA ) B ) C = ( AC )( BC ). The combinator S (in green) appears to be made by half of the 3-zipper, with some arrows and also with a 'diamond' added (all in blue). Interestingly, the diamond looks alike the ones from the emergent algebra sector, definition 5.4.
Expressed with the help of zippers, the relation SKK = I appears like this.
<details>
<summary>Image 45 Details</summary>
### Visual Description
## Diagram: Equivalent Representations of a System
### Overview
The image presents two equivalent diagrams representing a system. The diagram on the left is rendered in blue, while the equivalent diagram on the right is rendered in green. The two diagrams are separated by an equals sign made of three horizontal lines. Both diagrams have inputs labeled A, B, and C.
### Components/Axes
**Left Diagram (Blue):**
* **Inputs:** Labeled A, B, and C, exiting from the right side of a vertical rectangular block.
* **Vertical Block:** A rectangular block with three diagonal lines inside, each corresponding to an input (A, B, C). An arrow points upwards into the bottom of the block.
* **Bottom Component:** A diamond shape composed of four nodes connected by arrows. Each node contains a circle with a "Y" shape inside, except for the bottom node, which contains a "Y" shape without the circle. Arrows indicate the flow direction between the nodes.
* **Connections:** Curved lines connect the outputs A, B, and C to the nodes in the diamond shape.
**Right Diagram (Green):**
* **Inputs:** Labeled A, B, and C, exiting from the right side of a vertical chain of nodes.
* **Vertical Chain:** A series of nodes connected by arrows pointing upwards. The top two nodes are circles with a "Y" shape inside. Below them are three nodes containing a circle with a "λ" (lambda) symbol inside.
* **Bottom Component:** A diamond shape composed of four nodes connected by arrows. Each node contains a circle with a "Y" shape inside, except for the bottom node, which contains a "Y" shape without the circle. Arrows indicate the flow direction between the nodes.
* **Connections:** Curved lines connect the nodes containing "λ" to the nodes in the diamond shape.
### Detailed Analysis or ### Content Details
**Left Diagram (Blue):**
* Input A connects to the bottom-right node of the diamond.
* Input B connects to the top-right node of the diamond.
* Input C connects to the top-left node of the diamond.
**Right Diagram (Green):**
* The bottom node containing "λ" connects to the bottom-right node of the diamond.
* The middle node containing "λ" connects to the top-right node of the diamond.
* The top node containing "λ" connects to the top-left node of the diamond.
### Key Observations
* The two diagrams are visually distinct but represent the same underlying system.
* The vertical block in the left diagram is equivalent to the vertical chain of nodes with "λ" in the right diagram.
* The diamond-shaped component is identical in both diagrams.
* The connections between the inputs and the diamond component are re-routed through the vertical chain in the right diagram.
### Interpretation
The image illustrates two different ways to represent the same system or process. The left diagram uses a more compact representation with a vertical block, while the right diagram uses a more detailed representation with a chain of nodes containing "λ". The "λ" symbol likely represents a specific operation or transformation applied to the signals. The equivalence of the two diagrams suggests that the vertical block in the left diagram performs the same function as the chain of "λ" nodes in the right diagram. The diamond-shaped component likely represents a common processing element used in both representations. The diagram demonstrates how a complex system can be represented in multiple ways, each with its own advantages and disadvantages in terms of clarity and detail.
</details>
Lists and currying. With the help of zippers, we may enhance the procedure of turning grafting into the application operation. We have a graph A ∈ GRAPH which has one output and several inputs.
<details>
<summary>Image 46 Details</summary>
### Visual Description
## Diagram: Graph Reduction Steps
### Overview
The image depicts a series of graph transformations, likely representing a reduction or simplification process. The diagrams show directed graphs being modified through a sequence of steps, indicated by curved arrows. The graphs consist of nodes and edges, with specific node types labeled with symbols like "K" and "Y".
### Components/Axes
* **Nodes:** Represented by circles and rectangles. Some nodes are labeled with "K", "Y", or "λ".
* **Edges:** Represented by lines with arrowheads, indicating direction.
* **Transformation Arrows:** Curved arrows in blue indicate the transformation steps between the graphs.
* **Equivalence Symbol:** "|||" indicates equivalence between two graph states.
### Detailed Analysis
The diagram consists of six sub-diagrams arranged in a 2x3 grid. Each sub-diagram represents a state in the graph transformation process.
1. **Top-Left Diagram:**
* A vertical stack of four rectangular nodes. Each node has an incoming edge from the left, labeled "K" on the right side of the node.
* The bottom node of the stack has an outgoing edge that connects to a cluster of four circular nodes labeled "Y".
* The "Y" nodes are interconnected with edges forming a diamond shape.
* Edges connect the "Y" nodes back to the vertical stack.
2. **Top-Right Diagram:**
* Transformation from the top-left diagram is indicated by a blue curved arrow.
* Similar vertical stack of four rectangular nodes with incoming edges labeled "K".
* A cluster of three circular nodes labeled "Y".
* Two circular nodes labeled "λ".
* Edges connect these nodes in a more complex configuration compared to the top-left diagram.
3. **Middle-Center Diagram:**
* "|||" symbol indicating equivalence between the top-right and middle-left diagrams.
4. **Middle-Left Diagram:**
* Similar vertical stack of four rectangular nodes with incoming edges labeled "K".
* Two circular nodes labeled "Y".
* Edges connect these nodes in a simpler configuration compared to the top diagrams.
5. **Middle-Right Diagram:**
* Transformation from the middle-left diagram is indicated by a blue curved arrow.
* Similar vertical stack of four rectangular nodes with incoming edges labeled "K".
* Two circular nodes labeled "Y".
* Edges connect these nodes in a more complex configuration compared to the middle-left diagram.
6. **Bottom-Left Diagram:**
* Transformation from the middle-right diagram is indicated by a blue curved arrow.
* A vertical stack of one rectangular node with incoming edges labeled "K".
* One circular node labeled "Y".
* Edges connect these nodes in a simpler configuration compared to the middle diagrams.
7. **Bottom-Right Diagram:**
* Transformation from the bottom-left diagram is indicated by a blue curved arrow.
* A vertical stack of one rectangular node with incoming edges labeled "K".
* One circular node labeled "Y".
* Edges connect these nodes in a simpler configuration compared to the bottom-left diagram.
### Key Observations
* The number of rectangular nodes in the vertical stack decreases from four to one throughout the transformation process.
* The complexity of the connections between the circular nodes varies across the diagrams.
* The "K" labels remain consistent throughout the transformation.
* The "Y" and "λ" labels appear on circular nodes, suggesting different node types.
### Interpretation
The diagram illustrates a step-by-step reduction of a graph structure. The transformations appear to simplify the graph by reducing the number of nodes and edges while preserving certain key elements (e.g., "K" labels). The equivalence symbol "|||" suggests that the transformations maintain some form of functional equivalence despite the structural changes. The presence of "Y" and "λ" nodes indicates that the graph may represent a system with different types of components or operations. The overall process seems to be a simplification or optimization of the initial graph structure.
</details>
<details>
<summary>Image 47 Details</summary>
### Visual Description
## Diagram: Black Box with Inputs and Outputs
### Overview
The image shows a diagram of a black box labeled "A" with one input and multiple outputs. The outputs are labeled 1, 2, and n, suggesting a series of outputs.
### Components/Axes
* **Black Box:** A rectangle with rounded corners, labeled "A" in the center.
* **Input:** A single arrow pointing into the top of the black box.
* **Outputs:** Three arrows pointing out of the bottom of the black box. The arrows are labeled 1, 2, and n. The labels 1, 2, and n are in red. An ellipsis (...) is between the second and third output arrows, indicating that there are more outputs than shown.
### Detailed Analysis
* The diagram represents a system or function (A) that takes one input and produces multiple outputs.
* The ellipsis indicates that the number of outputs can vary or is not explicitly defined.
* The red labels 1, 2, and n likely represent indices or identifiers for each output.
### Key Observations
* The diagram is a simplified representation of a system with multiple outputs.
* The use of an ellipsis suggests a potentially large or variable number of outputs.
### Interpretation
The diagram illustrates a process where a single input is transformed or distributed into multiple outputs. This could represent a variety of systems, such as a signal splitter, a data processing unit, or a function that generates multiple results from a single input. The black box representation emphasizes that the internal workings of the system are not specified or relevant to the diagram's purpose, which is to show the input-output relationship.
</details>
We use an n-zipper in order to clip the inputs with the output.
<details>
<summary>Image 48 Details</summary>
### Visual Description
## Diagram: Process Flow Diagram
### Overview
The image is a process flow diagram illustrating a system with multiple inputs feeding into a series of components, culminating in a feedback loop. The diagram includes rectangular boxes representing processing units and arrows indicating the direction of flow.
### Components/Axes
* **Processing Units:** Represented by rectangular boxes. There are multiple boxes stacked vertically at the top and one larger box labeled "A" at the bottom.
* **Inputs:** Arrows pointing into the rectangular boxes on the right side, labeled "1", "2", and "n" in red.
* **Outputs:** Arrows pointing out of the rectangular boxes, indicating the flow of processed material.
* **Feedback Loop:** Curved arrows connecting the output of box "A" back to the inputs of the stacked boxes.
* **Flow Direction:** Indicated by arrows.
### Detailed Analysis
* **Top Stacked Boxes:** There are at least three stacked boxes at the top. The top box is labeled "n" on the right side. The second and third boxes are labeled "2" and "1" respectively, also on the right side. Each box has an input arrow pointing into its right side and an output arrow pointing out of its top.
* **Box A:** Located below the stacked boxes. It has an input arrow pointing into its top and multiple output arrows pointing out of its bottom. The outputs loop back to the inputs of the stacked boxes.
* **Flow:** The flow starts with inputs "1", "2", and "n" entering the stacked boxes. The outputs of these boxes feed into box "A". The outputs of box "A" are then fed back into the inputs of the stacked boxes, creating a feedback loop.
### Key Observations
* The diagram illustrates a system with multiple inputs and a feedback mechanism.
* The stacked boxes at the top appear to be processing units that receive inputs and produce outputs.
* Box "A" seems to be a central processing unit that receives inputs from the stacked boxes and distributes outputs back to them.
* The feedback loop suggests that the system is self-regulating or iterative.
### Interpretation
The diagram represents a process where multiple inputs are processed through a series of stages (the stacked boxes) and then fed into a central unit (box "A"). The outputs of the central unit are then fed back into the initial stages, creating a feedback loop. This type of system could represent a variety of processes, such as a chemical reaction, a control system, or a computational algorithm. The labels "1", "2", and "n" suggest that there are multiple inputs, possibly representing different parameters or variables. The feedback loop indicates that the system is dynamic and can adjust its behavior based on its outputs.
</details>
This graph is, in fact, the following one.
We may interpret the graph inside the green dotted rectangle as the currying of A , let's call him Curry ( A ). This graph has only one output and no inputs. The graph inside the red dotted rectangle is almost a list. We shall transform it into a list by using again a zipper and one graphic beta move.
<details>
<summary>Image 49 Details</summary>
### Visual Description
## Diagram: Network Architecture
### Overview
The image presents a diagram of a network architecture, likely representing a computational or information processing system. It features interconnected components, including a central block labeled "A," several circular nodes with the symbol "λ," and a series of nodes connected to external inputs labeled 1, 2, ..., n. The diagram uses arrows to indicate the direction of flow or data transmission.
### Components/Axes
* **Central Block:** A rectangular block labeled "A" at the bottom-center of the diagram.
* **Circular Nodes:** Several circular nodes, each containing the symbol "λ," are positioned vertically above the central block.
* **Input Nodes:** A series of nodes, each connected to an external input labeled with numbers 1, 2, ..., n, are located on the right side of the diagram.
* **Arrows:** Arrows indicate the direction of flow or data transmission between the components.
* **Green Dashed Box:** Encloses the central block "A" and the circular nodes with "λ" below the input nodes.
* **Red Dashed Box:** Encloses the input nodes labeled 1, 2, ..., n.
### Detailed Analysis
* **Central Block "A":** The central block "A" has multiple inputs at its bottom and a single output at its top.
* **Circular Nodes with "λ":** These nodes are arranged vertically above the central block. Each node receives an input from below and has two outputs: one directed upwards and another looping back towards the central block "A."
* **Input Nodes (1, 2, ..., n):** These nodes are arranged vertically on the right side of the diagram. Each node receives an external input (labeled 1, 2, ..., n) and connects to the main flow path.
* **Flow Direction:** The arrows indicate that the flow originates from the central block "A," passes through the circular nodes with "λ," and eventually connects to the input nodes (1, 2, ..., n). The loops from the circular nodes with "λ" back to the central block "A" suggest a feedback mechanism.
* **Positioning:** The red dashed box is located on the top-right of the diagram. The green dashed box is located on the left side of the diagram.
### Key Observations
* The diagram illustrates a network with a central processing unit ("A") and feedback loops.
* The input nodes (1, 2, ..., n) provide external inputs to the network.
* The circular nodes with "λ" likely represent some form of processing or transformation of the data.
### Interpretation
The diagram likely represents a recurrent neural network or a similar computational architecture. The central block "A" could represent a core processing unit, while the circular nodes with "λ" could represent layers or units within the network. The feedback loops suggest that the network's output is fed back into the input, allowing it to learn and adapt over time. The input nodes (1, 2, ..., n) provide external data to the network, which is then processed and transformed by the network's internal components. The architecture suggests a system capable of processing sequential data or learning complex patterns.
</details>
Packing arrows. We may pack several arrows into one. I describe first the case of two arrows. We start from the following sequence of three graphic beta moves.
<details>
<summary>Image 50 Details</summary>
### Visual Description
## Diagram: List Construction with Curry
### Overview
The image is a diagram illustrating the construction of a list using a combination of lambda abstraction and a "Curry" operation. It shows a series of operations within a dashed red box labeled "List(1,2,...,n)" and a "Curry(A)" operation outside the box in a dashed green box. The diagram uses arrows to indicate the flow of data or operations.
### Components/Axes
* **Red Dashed Box:** Labeled "List(1,2,...,n)" at the top. This box encapsulates the list construction process.
* **Green Dashed Box:** Labeled "Curry(A)" at the top-right. Represents a currying operation.
* **Lambda Abstraction (λ):** A circle containing the lambda symbol (λ) at the top of the red box.
* **"Apply" Operator (人):** A circle containing a symbol resembling an upside-down "V" (referred to as "Apply" operator for clarity). This operator appears multiple times within the red box.
* **Input Values:** The numbers 1, 2, ..., n, shown in red, are inputs to the "Apply" operators.
* **Arrows:** Indicate the direction of data flow or operation execution.
### Detailed Analysis
1. **List Construction:**
* The process starts with a lambda abstraction (λ).
* A series of "Apply" operators (人) are arranged vertically.
* Each "Apply" operator takes an input value (1, 2, ..., n). The values are in red.
* The output of each "Apply" operator feeds into the next one in the series.
* The final output loops back to the lambda abstraction (λ).
2. **Curry Operation:**
* The output of the lambda abstraction also feeds into another "Apply" operator (人) outside the red box.
* This "Apply" operator also receives input from the "Curry(A)" box.
* The output of this final "Apply" operator is not explicitly shown.
### Key Observations
* The diagram illustrates a recursive or iterative process for constructing a list.
* The "Curry(A)" operation seems to be applied to the result of the list construction.
* The "Apply" operator (人) is a key component in both the list construction and the currying operation.
### Interpretation
The diagram likely represents a functional programming concept where a list is constructed by repeatedly applying a function (represented by the "Apply" operator) to a series of input values. The lambda abstraction (λ) likely defines the function that is being applied. The "Curry(A)" operation suggests that the function is being curried, which means that it is being transformed into a function that takes its arguments one at a time. The entire process constructs a list and then applies a currying operation to the result, possibly to prepare it for further processing or evaluation. The diagram highlights the use of functional programming techniques like lambda abstraction, function application, and currying in the context of list construction.
</details>
With words, this figure means: we pack the 1, 2, entries into a list, we pass it trough one
<details>
<summary>Image 51 Details</summary>
### Visual Description
## Diagram: State Transition Diagram with Lambda and Beta Transformations
### Overview
The image presents a series of state transition diagrams, illustrating transformations between different configurations. Each diagram consists of nodes, edges (arrows), and labels, representing states and transitions between them. The transformations are mediated by operators denoted as "λ" and "β".
### Components/Axes
* **Nodes:** Represented by circles, some containing the symbol "λ".
* **Edges:** Represented by arrows, indicating the direction of flow or transformation.
* **Labels:** Numerical labels (1, 2, 3, 4) are placed near the edges, likely representing input/output channels or states.
* **Transformation Operator:** "β" (beta) is represented by a curved blue arrow, indicating a transformation between states.
* **Dotted Red Ovals:** Highlight specific regions or components within the diagrams.
### Detailed Analysis
**Top Diagram:**
* Two input arrows labeled "1" and "2" converge into a node.
* Two output arrows labeled "3" and "4" emerge from a node.
* Two nodes in the center are enclosed by a dotted red oval. One node contains the symbol "λ".
* The top node splits into two nodes, one with "λ" and one without.
* The bottom node splits into two nodes, one with "λ" and one without.
**Second Diagram:**
* The diagram is a transformation of the first diagram, indicated by the "β" operator.
* The input arrows labeled "1" and "2" now cross over before reaching the output nodes labeled "3" and "4".
* The dotted red oval now encloses two nodes on the left side of the diagram. One node contains the symbol "λ".
**Third Diagram:**
* The diagram is a transformation of the second diagram, indicated by the "β" operator.
* Input arrow "1" leads directly to output arrow "3".
* Input arrow "2" goes through two nodes, each with "λ", before becoming output arrow "4". The path of arrow "2" crosses itself.
**Bottom Diagram:**
* The diagram is a transformation of the third diagram, indicated by the "β" operator.
* Input arrow "1" leads directly to output arrow "3".
* Input arrow "2" leads directly to output arrow "4".
### Key Observations
* The "β" operator appears to mediate transformations between different configurations of nodes and edges.
* The "λ" symbol within the nodes might represent a specific operation or property associated with that node.
* The dotted red ovals highlight specific regions undergoing transformation.
* The numerical labels (1, 2, 3, 4) remain consistent throughout the transformations, suggesting they represent fixed input/output channels.
### Interpretation
The diagram illustrates a series of transformations between different states or configurations. The "β" operator seems to represent a transformation rule or process that alters the connections and relationships between nodes. The "λ" symbol likely represents a specific operation or property associated with a node, and its presence or absence influences the overall transformation. The diagram could represent a simplified model of a physical system, a computational process, or a mathematical relationship. The transformations show how input channels (1, 2) are re-routed or processed to produce different output channels (3, 4). The red ovals highlight the regions where the most significant changes occur during each transformation step.
</details>
arrow then we unpack the list into the outputs 3, 4. This packing-unpacking trick may be used of course for more than a pair of arrows, in obvious ways, therefore it is not a restriction of generality to write only about two arrows.
We may apply the trick to a pair of graphs A and B , which are connected by a pair of arrows, like in the following figure.
<details>
<summary>Image 52 Details</summary>
### Visual Description
## Diagram: Transformation of a System
### Overview
The image depicts a transformation of a system represented by two diagrams. The top diagram shows a direct connection between two components, A and B, with multiple inputs and outputs. The bottom diagram shows a modified connection between A and B, involving intermediate components and loops, also with multiple inputs and outputs. A curved blue arrow indicates the transformation between the two states.
### Components/Axes
* **Components:**
* Box labeled "A" (appears in both diagrams)
* Box labeled "B" (appears in both diagrams)
* Intermediate components (only in the bottom diagram):
* Two components resembling a circle with a line through it.
* Two components labeled "λ" (lambda).
* **Connections:** Arrows indicate the flow of information or energy.
* **Transformation Arrow:** A curved blue arrow pointing downwards, indicating the transformation from the top diagram to the bottom diagram.
### Detailed Analysis
**Top Diagram:**
* **Component A:** Has three inputs on the left and two outputs on the right.
* **Component B:** Has two inputs on the left (connected to the outputs of A) and three outputs on the right.
* **Connection between A and B:** The two outputs of A cross over to become the two inputs of B.
**Bottom Diagram:**
* **Component A:** Has three inputs on the left. The output of A is connected to two components resembling a circle with a line through it.
* **Intermediate Components:**
* The two components resembling a circle with a line through it are connected to a component labeled "λ" (lambda).
* The two "λ" components are connected to each other, forming a loop.
* The output of the loop is connected to another component labeled "λ" (lambda).
* The output of the second "λ" component is connected to two components resembling a circle with a line through it.
* **Component B:** Has three outputs on the right.
* **Connection between A and B:** The connection between A and B is mediated by the intermediate components and the loop.
### Key Observations
* The transformation involves introducing intermediate components and a feedback loop between the components A and B.
* The number of inputs and outputs for components A and B remains the same in both diagrams.
* The transformation arrow suggests a change in the internal structure or interaction between A and B.
### Interpretation
The diagram illustrates a transformation of a system, where the direct interaction between components A and B is replaced by a more complex interaction involving intermediate components and a feedback loop. This transformation could represent a change in the system's behavior, stability, or sensitivity to external inputs. The "λ" components likely represent parameters or variables that influence the system's dynamics. The introduction of the loop suggests a potential for feedback and self-regulation within the system. The components resembling a circle with a line through it may represent a specific type of interaction or operation within the system.
</details>
With the added packing and unpacking triples of gates, the graphs A , B are interacting only by the intermediary of one arrow.
In particular, we may use this trick for the elementary gates of abstraction and application, transforming them into graphs with one input and one output, like this:
<details>
<summary>Image 53 Details</summary>
### Visual Description
## Diagram: Feynman Diagram Transformations
### Overview
The image presents two rows of diagrams, each depicting a transformation of a Feynman diagram. Each row starts with a simple diagram, transitions via a green wavy arrow, and ends with a more complex diagram. The diagrams involve vertices, internal lines, and external lines, with some vertices labeled with "λ".
### Components/Axes
* **Vertices:** Represented by circles, some containing the label "λ".
* **Lines:** Represented by arrows, indicating the direction of particle flow.
* **Green Wavy Arrows:** Indicate a transformation or equivalence between the diagrams.
### Detailed Analysis
**Row 1:**
1. **Initial Diagram:** A vertex labeled "λ" with one incoming line and two outgoing lines.
2. **Transformation:** A green wavy arrow pointing to the right.
3. **Final Diagram:** A more complex diagram consisting of four vertices. Three vertices are labeled "λ". The diagram has one incoming line and one outgoing line. The vertices are connected by internal lines with arrows indicating flow.
**Row 2:**
1. **Initial Diagram:** A vertex labeled "λ" with two incoming lines and one outgoing line.
2. **Transformation:** A green wavy arrow pointing to the right.
3. **Final Diagram:** A more complex diagram consisting of four vertices. Two vertices are labeled "λ". The diagram has one incoming line and one outgoing line. The vertices are connected by internal lines with arrows indicating flow.
### Key Observations
* The green wavy arrows indicate a transformation or equivalence between the diagrams on either side.
* The diagrams represent interactions between particles, with the arrows indicating the direction of particle flow.
* The "λ" label likely represents a coupling constant or interaction strength.
* The transformations increase the complexity of the diagrams, suggesting a process of expanding or resolving interactions.
### Interpretation
The diagrams illustrate a process of transforming Feynman diagrams, possibly representing a simplification or expansion of interactions in a quantum field theory calculation. The green wavy arrows suggest that the diagrams on either side are equivalent in some sense, perhaps representing different ways of calculating the same physical process. The "λ" labels likely represent coupling constants, which determine the strength of the interactions. The transformations may be used to simplify calculations or to reveal underlying structures in the theory.
</details>
If we use the elementary gates transformed into graphs with one input and one output, the graphic beta move becomes this almost algebraic, 1D rule:
<details>
<summary>Image 54 Details</summary>
### Visual Description
## Diagram: Feynman Diagram Transformation
### Overview
The image presents two Feynman diagrams and a transformation arrow between them. The top diagram is a more complex representation, while the bottom diagram is a simplified version. The transformation is labeled with "β".
### Components/Axes
* **Nodes:** Represented by circles, some containing the symbol "λ".
* **Lines:** Represented by arrows, indicating the direction of particle flow.
* **External Legs:** Labeled with numbers 1, 2, 3, and 4, indicating incoming or outgoing particles.
* **Transformation Arrow:** A curved blue arrow labeled "β" indicating the transformation from the complex diagram to the simplified diagram.
### Detailed Analysis
**Top Diagram:**
* **Left Side:** Starts with an incoming line labeled "1". This line connects to a node containing "λ". This node is connected to a complex structure of two nodes with "λ" inside, connected by two lines with arrows in opposite directions. This structure is connected to another node with "λ".
* **Middle Section:** The diagram continues with a series of nodes, some containing "λ". There is a branching point where a line goes downwards to an outgoing line labeled "2".
* **Right Side:** The diagram continues with a triangular structure of nodes containing "λ". This structure is connected to a diamond-shaped structure of nodes containing "λ". The diagram ends with an outgoing line labeled "3".
* **Top Branch:** A line goes upwards from the triangular structure to an outgoing line labeled "4".
**Bottom Diagram:**
* A simplified diagram with four lines intersecting at a single point.
* Incoming line labeled "1" on the left.
* Outgoing line labeled "3" on the right.
* Outgoing line labeled "2" going downwards.
* Incoming line labeled "4" coming from the top.
* **Transformation:** The blue curved arrow labeled "β" indicates the transformation from the top diagram to the bottom diagram.
### Key Observations
* The top diagram represents a more detailed interaction, while the bottom diagram represents a simplified version of the same interaction.
* The transformation "β" simplifies the complex interaction into a single vertex interaction.
* The "λ" symbol within the nodes likely represents a coupling constant or interaction strength.
### Interpretation
The image illustrates a simplification process in Feynman diagrams. The complex diagram in the top represents a higher-order interaction, which can be approximated by the simpler diagram in the bottom. The transformation "β" represents the process of reducing the complex interaction to its lowest-order approximation. This type of simplification is common in quantum field theory calculations, where higher-order diagrams are often neglected due to their smaller contributions. The parameter "λ" likely represents a coupling constant, and the diagram shows how a complex interaction involving multiple couplings can be approximated by a single effective coupling.
</details>
With such procedures, we may transform any graph in GRAPH into a 1D string of graphs, consisting of transformed elementary graphs and packers and un-packers of arrows, which could be used, in principle, for transforming graphic lambda calculus into a text programming language.
## 5 Emergent algebras
Emergent algebras [3] [4] are a distillation of differential calculus in metric spaces with dilations [2]. This class of metric spaces contain the 'classical' riemannian manifolds, as well as fractal like spaces as Carnot groups or, more general, sub-riemannian or CarnotCarath´ eodory spaces, Bella¨ ıche [1], Gromov [11], endowed with an intrinsic differential calculus based on some variant of the Pansu derivative [18].
In [2] section 4 Binary decorated trees and dilatations, I propose a formalism for making easy various calculations with dilation structures. This formalism works with moves acting on binary decorated trees, with the leaves decorated with elements of a metric space.
Here is an example of the formalism. The moves are (with same names as those used in graphic lambda calculus, see the explanation further):
<details>
<summary>Image 55 Details</summary>
### Visual Description
## Diagram: Tree Transformations
### Overview
The image depicts two tree transformation rules, R1a and R2a. Each rule shows a transformation between a tree structure and a single node. The nodes in the trees are labeled with 'A' or 'B', and the nodes themselves are either filled (black) or unfilled (white).
### Components/Axes
* **Nodes:** Represented as circles, either filled (black) or unfilled (white).
* **Edges:** Represented as lines connecting the nodes, forming a tree structure.
* **Labels:** 'A' and 'B' are used to label the leaf nodes of the trees.
* **Transformation Rules:** R1a and R2a, indicated by blue double-headed arrows.
### Detailed Analysis
**Row 1: Transformation Rule R1a**
* **Left:** A tree with a root node (unfilled) and two child nodes labeled 'A' and 'A'.
* **Transformation:** The rule R1a transforms this tree into a single node labeled 'A'.
* **Right:** A tree with a root node (filled) and two child nodes labeled 'A' and 'A'.
* The transformation is reversible, as indicated by the double-headed arrow.
**Row 2: Transformation Rule R2a**
* **Left:** A tree with a root node (filled), a left child node labeled 'A', and a right child node which is a subtree. This subtree has a root node (unfilled) and a child node labeled 'A' and 'B'.
* **Transformation:** The rule R2a transforms this tree into a single node labeled 'B'.
* **Right:** A tree with a root node (unfilled), a left child node labeled 'A', and a right child node which is a subtree. This subtree has a root node (filled) and a child node labeled 'A' and 'B'.
* The transformation is reversible, as indicated by the double-headed arrow.
### Key Observations
* The rules R1a and R2a define transformations between tree structures and single nodes.
* The filled/unfilled state of the nodes seems to be significant, as it changes during the transformation.
* The labels 'A' and 'B' appear to be related to the structure of the tree.
### Interpretation
The diagram illustrates a set of tree transformation rules. These rules likely form part of a larger system for manipulating or simplifying tree structures. The filled/unfilled state of the nodes could represent different types or properties of the nodes, and the labels 'A' and 'B' could represent different categories or values associated with the nodes. The transformations could be used to reduce complex trees to simpler representations, or to perform other operations on the trees. The specific meaning of the nodes, edges, and labels would depend on the context in which these rules are used.
</details>
Define the following graph (and think about it as being the graphical representation of an operation u + v with respect to the basepoint x ):
<details>
<summary>Image 56 Details</summary>
### Visual Description
## Diagram: Tree Transformation
### Overview
The image presents a diagram illustrating a transformation of a tree structure. On the left, a tree with a node represented by a circle containing a plus sign is shown. This is equivalent to a more complex tree structure on the right, which involves nodes represented by filled and unfilled circles. The diagram demonstrates how a single node operation can be decomposed into a more detailed tree structure.
### Components/Axes
* **Left Tree:**
* Root Node: A circle with a "+" sign inside, labeled "x" to the right.
* Child Nodes: Two nodes labeled "u" and "v" connected to the root node.
* Edges: Lines connecting the nodes.
* **Equality Symbol:** Three horizontal lines indicating equivalence.
* **Right Tree:**
* Top Node: A filled circle.
* Second Level Nodes: One node labeled "x" connected to the top node. Another node (unfilled circle) connected to the top node.
* Third Level Nodes: One node labeled "v" connected to the unfilled circle. Another node (unfilled circle) connected to the unfilled circle.
* Bottom Nodes: Two nodes labeled "x" and "u" connected to the unfilled circle.
* Edges: Lines connecting the nodes.
### Detailed Analysis or Content Details
The left side of the diagram shows a tree with a root node that performs an addition operation (indicated by the "+" sign). This node has two children, labeled "u" and "v". The right side of the diagram shows an equivalent tree structure. The top node is a filled circle, which could represent a specific operation or state. This node has two children: one labeled "x" and another represented by an unfilled circle. The unfilled circle node further branches into "v" and another unfilled circle, which then branches into "x" and "u".
### Key Observations
* The transformation replaces a single node operation (addition) with a more complex tree structure.
* The filled and unfilled circles likely represent different types of operations or states within the tree.
* The labels "x", "u", and "v" represent variables or values being processed by the tree.
### Interpretation
The diagram illustrates a transformation or decomposition of an operation within a tree structure. The addition operation on the left is replaced by a more detailed tree on the right, which likely represents a series of operations or states. The filled and unfilled circles likely represent different types of operations or states, and the labels "x", "u", and "v" represent the data being processed. This type of transformation could be used to optimize or simplify complex operations within a tree-based system.
</details>
Then, in the binary trees formalism I can prove, by using the moves R1a, R2a, the following 'approximate' associativity relation (it is approximate because there appear a basepoint which is different from x , but which, in the geometric context of spaces with dilations, is close to x ):
×
<details>
<summary>Image 57 Details</summary>
### Visual Description
## Diagram: Tree Transformation
### Overview
The image depicts a transformation of a tree structure, likely representing an algebraic expression. The transformation involves rearranging the nodes and branches of the tree while preserving the underlying mathematical meaning. The diagram shows two trees connected by a double-headed arrow, indicating a reversible transformation.
### Components/Axes
* **Nodes:** Each node is represented by a circle containing a "+" symbol, indicating an addition operation.
* **Branches:** Lines connecting the nodes represent the relationships between the operations and operands.
* **Leaves:** The terminal nodes of the tree are labeled with variables: u, x, y, and z.
* **Arrow:** A blue double-headed arrow indicates the transformation direction.
* **Labels:** The variables x, y, z, and u are used as labels.
### Detailed Analysis
**Left Tree:**
* The root node (top) is a "+" node labeled with "x".
* The left child of the root is labeled "u".
* The right child of the root is another "+" node labeled with "x".
* The left child of the second "+" node is labeled "y".
* The right child of the second "+" node is labeled "z".
* There is a small dangling node with a circle, labeled "x" and "u".
**Right Tree:**
* The root node (top) is a "+" node labeled with "x".
* The left child of the root is another "+" node labeled with "x".
* The right child of the root is labeled "z".
* The left child of the second "+" node is labeled "u".
* The right child of the second "+" node is labeled "y".
**Transformation:**
* The double-headed arrow indicates that the transformation can occur in either direction.
* The transformation essentially rearranges the order of addition, grouping "u" and "y" together before adding "z".
### Key Observations
* The transformation appears to be an application of the associative property of addition.
* The dangling node on the left tree is not present on the right tree, suggesting it might be an intermediate step or a simplification.
### Interpretation
The diagram illustrates the associative property of addition, which states that the grouping of operands in an addition operation does not affect the result. The transformation shows how the tree structure can be rearranged to reflect different groupings of the same operands. The dangling node on the left tree might represent a temporary variable or an intermediate calculation that is simplified in the final expression. The diagram demonstrates the flexibility in representing mathematical expressions and how they can be manipulated while preserving their meaning.
</details>
It was puzzling that in fact the formalism worked without needing to know which metric space is used. Moreover, reasoning with moves acting on binary trees gave proofs of generalizations of results from sub-riemannian geometry, while classical proofs involve elaborate calculations with pseudo-differential operators. At a close inspection it looked like some-
where in the background there is an abstract nonsense machine which is just applied to the particular case of sub-riemannian spaces.
In this paper I shall take the following pure algebraic definition of an emergent algebra (compare with definition 5.1 [3]), which is a stronger version of the definition 4.2 [4] of a Γ idempotent right quasigroup, in the sense that here I define a Γ idempotent quasigroup.
Definition 5.1 Let Γ be a commutative group with neutral element denoted by 1 and operation denoted multiplicatively. A Γ idempotent quasigroup is a set X endowed with a family of operations ◦ ε : X × X → X , indexed by ε ∈ Γ , such that:
- -For any ε ∈ Γ \ { 1 } the pair ( X, ◦ ε ) is an idempotent quasigroup, i.e. for any a, b ∈ X the equations x ◦ ε a = b and a ◦ ε x = b have unique solutions and moreover x ◦ ε x = x for any x ∈ X ,
- -The operation ◦ 1 is trivial: for any x, y ∈ X we have x ◦ 1 y = y ,
- -For any x, y ∈ X and any ε, µ ∈ Γ we have: x ◦ ε ( x ◦ µ y ) = x ◦ εµ y .
Here are some examples of Γ idempotent quasigroups.
Example 1. Real (or complex) vector spaces: let X be a real (complex) vector space, Γ = (0 , + ∞ ) (or Γ = C ∗ ), with multiplication as operation. We define, for any ε ∈ Γ the following quasigroup operation: x ◦ ε y = (1 -ε ) x + εy . These operations give to X the structure of a Γ idempotent quasigroup. Notice that x ◦ ε y is the dilation based at x , of coefficient ε , applied to y .
Example 2. Contractible groups: let G be a group endowed with a group morphism φ : G → G . Let Γ = Z with the operation of addition of integers (thus we may adapt definition 5.1 to this example by using ' ε + µ ' instead of ' εµ ' and '0' instead of '1' as the name of the neutral element of Γ). For any ε ∈ Z let x ◦ ε y = xφ ε ( x -1 y ). This a Z idempotent quasigroup. The most interesting case is the one when φ is an uniformly contractive automorphism of a topological group G . The structure of these groups is an active exploration area, see for example [12] and the bibliography therein. A fundamental result here is Siebert [20], which gives a characterization of topological connected contractive locally compact groups as being nilpotent Lie groups endowed with a one parameter family of dilations, i.e. almost Carnot groups.
Example 3. A group with an invertible self-mapping φ : G → G such that φ ( e ) = e , where e is the identity of the group G . It looks like Example 2 but it shows that there is no need for φ to be a group morphism.
Local versions. We may accept that there is a way (definitely needing care to well formulate, but intuitively clear) to define a local version of the notion of a Γ idempotent quasigroup. With such a definition, for example, a convex subset of a real vector space gives a local (0 , + ∞ ) idempotent quasigroup (as in Example 1) and a neighbourhood of the identity of a topological group G , with an identity preserving, locally defined invertible self map (as in Example 3) gives a Z local idempotent quasigroup.
Example 4. A particular case of Example 3 is a Lie group G with the operations defined for any ε ∈ (0 , + ∞ ) by x ◦ ε y = x exp( ε log( x -1 y )).
Example 5. A less symmetric example is the one of X being a riemannian manifold, with associated operations defined for any ε ∈ (0 , + ∞ ) by x ◦ ε y = exp x ( ε log x ( y )), where exp is the metric exponential.
Example 6. More generally, any metric space with dilations is a local idempotent (right) quasigroup.
Example 7. One parameter deformations of quandles. A quandle is a self-distributive quasigroup. Take now a one-parameter family of quandles (indexed by ε ∈ Γ) which satisfies moreover points 2. and 3. from definition 5.1. What is interesting about this example is that quandles appear as decorations of knot diagrams [10] [13], which are preserved by the Reidemeister moves (more on this in the section 6). At closer examination, examples 1, 2 are particular cases of one parameter quandle deformations!
I define now the operations of approximate sum and approximate difference associated to a Γ idempotent quasigroup.
Definition 5.2 For any ε ∈ Γ we give the following names to several combinations of operations of emergent algebras:
- -the approximate sum operation is Σ x ε ( u, v ) = x · ε (( x ◦ ε u ) ◦ ε v ) ,
- -the approximate difference operation is ∆ x ε ( u, v ) = ( x ◦ ε u ) · ε ( x ◦ ε v ) ,
- -the approximate inverse operation is inv x ε u = ( x ◦ ε u ) · ε x .
Let's see what the approximate sum operation is, for example 1.
$$\Sigma _ { \varepsilon } ^ { x } ( u , v ) = u ( 1 - \varepsilon ) - x + v$$
It is clear that, as ε converges to 0, this becomes the operation of addition in the vector space with x as neutral element, so it might be said that is the operation of addition of vectors in the tangent space at x , where x is seen as an element of the affine space constructed over the vector space from example 1.
This is a general phenomenon, which becomes really interesting in non-commutative situations, i.e. when applied to examples from the end of the provided list.
These approximate operations have many algebraic properties which can be found by the abstract nonsense of manipulating binary trees.
Another construction which can be done in emergent algebras is the one of taking finite differences (at a high level of generality, not bonded to vector spaces).
Definition 5.3 Let A : X → X be a function (from X to itself, for simplicity). The finite difference function associated to A , with respect to the emergent algebra over X , at a point x ∈ X is the following.
$$T _ { \varepsilon } ^ { x } A \colon X \to X \quad , \quad T _ { \varepsilon } ^ { x } A ( u ) = A ( x ) \bullet _ { \varepsilon } \left ( A \left ( x \circ _ { \varepsilon } u \right ) \right )$$
For example 1, the finite difference has the expression:
$$T _ { \varepsilon } ^ { x } A ( u - x ) = A ( x ) + \frac { 1 } { \varepsilon } \left ( A ( x + \varepsilon u ) - A ( x ) \right )$$
which is a finite difference indeed. In more generality, for example 2 this definition leads to the Pansu derivative [18].
Finite differences as defined here behave like discrete versions of derivatives. Again, the proofs consist in manipulating well chosen binary trees.
All this can be formalized in graphic lambda calculus, thus transforming the proofs into computations inside graphic lambda calculus.
I shall not insist more on this, with the exception of describing the emergent algebra sector of graphic lambda calculus.
Definition 5.4 For any ε ∈ Γ , the following graphs in GRAPH are introduced:
- -the approximate sum graph Σ ε
<details>
<summary>Image 58 Details</summary>
### Visual Description
## Diagram: Diamond-Shaped Flow Diagram
### Overview
The image is a flow diagram in the shape of a diamond, with arrows indicating the direction of flow. The diagram consists of four nodes at the corners of the diamond, each containing a symbol or value.
### Components/Axes
* **Nodes:** Four circular nodes labeled with symbols: ε⁻¹, ε, ε, and γ.
* **Arrows:** Arrows indicate the direction of flow between the nodes.
* **External Arrows:** Arrows entering and exiting the diagram at each node.
### Detailed Analysis
The diagram shows a flow of information or process through a diamond-shaped network.
* **Top Node:** Contains the symbol ε⁻¹. Arrows enter from the left and exit upwards.
* **Right Node:** Contains the symbol ε. Arrows enter from the top-right and exit to the right.
* **Bottom Node:** Contains the symbol ε. Arrows enter from the right and exit downwards.
* **Left Node:** Contains the symbol γ. Arrows enter from the left and exit to the left.
The arrows connect the nodes in a clockwise direction around the diamond.
### Key Observations
* The diagram represents a cyclical process or flow.
* The symbols ε⁻¹, ε, and γ likely represent specific operations or transformations.
* The arrows indicate the direction of the process.
### Interpretation
The diagram likely represents a mathematical or physical process where a quantity is transformed as it flows through the network. The symbols ε⁻¹, ε, and γ represent specific operations or transformations applied to the quantity at each node. The cyclical nature of the diagram suggests that the process may be iterative or self-reinforcing. The exact meaning of the diagram would depend on the context in which it is used.
</details>
-the approximate difference graph ∆ ε
<details>
<summary>Image 59 Details</summary>
### Visual Description
## Diagram: Symbolic Representation of a Process
### Overview
The image is a diagram composed of interconnected nodes and directed edges (arrows), representing a process or system. The nodes are labeled with symbols, and the arrows indicate the direction of flow or relationship between the nodes. The diagram is symmetrical and appears to represent a cyclical or iterative process.
### Components/Axes
* **Nodes:**
* ε (epsilon): Appears twice in the diagram.
* ε⁻¹ (epsilon inverse): Appears once.
* γ (gamma): Appears once.
* **Edges:** Directed arrows connecting the nodes, indicating the flow or relationship between them.
* **Directionality:** Arrows indicate the direction of the process flow.
### Detailed Analysis
The diagram consists of four nodes arranged in a diamond shape. Each node is connected to its adjacent nodes by directed edges (arrows).
* **Top Node:** Labeled ε⁻¹. Two arrows point away from this node, one to the left and one to the right.
* **Left Node:** Labeled ε. One arrow points towards this node from the top node (ε⁻¹), and one arrow points away from this node to the bottom node (γ). There is also an arrow pointing into the node from the left.
* **Right Node:** Labeled ε. One arrow points towards this node from the top node (ε⁻¹), and one arrow points away from this node to the bottom node (γ). There is also an arrow pointing away from the node to the right.
* **Bottom Node:** Labeled γ. Two arrows point towards this node, one from the left node (ε) and one from the right node (ε). One arrow points away from this node downwards.
Additionally, there is an arrow pointing upwards towards the top node (ε⁻¹) and an arrow pointing downwards away from the bottom node (γ).
### Key Observations
* The diagram is symmetrical about the vertical axis.
* The nodes are interconnected in a cyclical manner.
* The arrows indicate a specific direction of flow or relationship between the nodes.
### Interpretation
The diagram represents a process or system where elements (represented by ε, ε⁻¹, and γ) interact with each other in a specific sequence. The arrows indicate the direction of flow or transformation. The presence of ε and its inverse (ε⁻¹) suggests a reversible or balancing process. The gamma (γ) node might represent a result or output of the process. The cyclical nature of the diagram suggests an iterative or feedback loop. The additional arrows pointing into the left node (ε) and away from the right node (ε) could represent external inputs or outputs to the system.
</details>
-the approximate inverse graph inv ε
<details>
<summary>Image 60 Details</summary>
### Visual Description
## Diagram: Knot Diagram with Labels
### Overview
The image is a knot diagram, a type of mathematical representation used to visualize and analyze knots. It consists of lines and circles, with arrows indicating the direction of flow or orientation. The diagram includes labels within the circles, specifically epsilon, epsilon inverse, and a Y-like symbol.
### Components/Axes
* **Nodes:** Three circular nodes are present in the diagram.
* Top node: Labeled "ε⁻¹" (epsilon inverse).
* Middle-left node: Labeled "ε" (epsilon).
* Bottom node: Labeled "Y" (a Y-shaped symbol).
* **Lines/Edges:** Lines connect the nodes, representing strands of the knot. Arrows on the lines indicate direction.
* **Arrows:** Arrows indicate the direction of flow along the lines.
* **External Lines:** Two lines extend from the top and bottom of the diagram, each with an arrow pointing upwards.
### Detailed Analysis
* **Top Node (ε⁻¹):**
* One line enters the node from the middle-left (ε) node, flowing upwards.
* One line enters the node from the bottom (Y) node, flowing upwards and curving to the right.
* One line exits the node upwards, continuing the flow.
* **Middle-Left Node (ε):**
* One line enters the node from the top (ε⁻¹) node, flowing downwards.
* One line exits the node horizontally to the right.
* One line exits the node downwards towards the bottom (Y) node.
* **Bottom Node (Y):**
* One line enters the node from the middle-left (ε) node, flowing downwards.
* One line enters the node from the top (ε⁻¹) node, flowing downwards.
* One line exits the node downwards, continuing the flow.
### Key Observations
* The diagram represents a flow or transformation process, with the arrows indicating the direction of the process.
* The epsilon and epsilon inverse nodes suggest an inverse relationship or operation.
* The Y-shaped symbol at the bottom node might represent a branching or merging point in the process.
### Interpretation
The diagram likely represents a mathematical or physical process involving transformations and relationships between different elements. The epsilon and epsilon inverse nodes could represent a variable and its inverse, while the Y-shaped node could represent a point where two inputs are combined into a single output. The overall structure suggests a cyclical or iterative process, with the flow returning to the starting point. The specific meaning of the diagram would depend on the context in which it is used.
</details>
Let A be a set of symbols a, b, c, ... . (These symbols will play the role of scale parameters going to 0.) With A and with the abelian group Γ we construct a larger abelian group, call it ¯ Γ, which is generated by A and by Γ.
Now we introduce the emergent algebra sector (over the set A ).
Definition 5.5 EMER ( A ) is the subset of GRAPH (over the group ¯ Γ ) which is generated by the following list of gates:
- -arrows and loops,
- -Υ gate and the gates ¯ ε for any ε ∈ Γ ,
- -the approximate sum gate Σ a and the approximate difference gate ∆ a , for any a ∈ A ,
with the operations of linking output to input arrows and with the following list of moves:
- FAN-OUT moves
- -emergent algebra moves for the group ¯ Γ ,
- -¡pruning moves.
The set EMER ( A ) with the given list of moves is called the emergent algebra sector over the set A .
The approximate inverse is not included into the list of generating gates. That is because we can prove easily that for any a ∈ A we have inv a ∈ EMER ( A ). (If ε ∈ Γ then we trivially have inv ε ∈ EMER ( A ) because it is constructed from emergent algebra gates decorated by elements in Γ, which are on the list of generating gates.) Here is the proof: we start with the approximate difference ∆ a and with an Υ gate and we arrive to the approximate inverse inv a by a sequence of moves, as follows.
<details>
<summary>Image 61 Details</summary>
### Visual Description
## Diagram: Category Theory Transformations
### Overview
The image depicts a series of transformations in category theory, represented by diagrams with nodes and arrows. The transformations are labeled as "CO-ASSOC" and "R1a". The diagrams show how different compositions of morphisms (represented by the nodes and arrows) are equivalent under these transformations.
### Components/Axes
* **Nodes:** Represented by circles, labeled with "a", "a<sup>-1</sup>", or a "Y" symbol. These likely represent objects or morphisms in a category.
* **Arrows:** Indicate the direction of morphisms or transformations between objects.
* **Labels:**
* "CO-ASSOC": Indicates a co-associativity transformation.
* "R1a": Indicates a specific rule or transformation, possibly related to a right identity.
### Detailed Analysis
The image can be broken down into three distinct diagrams, connected by transformation arrows.
**Diagram 1 (Top-Left):**
* A node labeled "a<sup>-1</sup>" is at the top.
* Two nodes labeled "a" are on the left and right sides, slightly below the top node.
* Two nodes with the "Y" symbol are at the bottom.
* Arrows connect the nodes, forming a network. One arrow points from the left "a" node back towards the "a<sup>-1</sup>" node.
* One arrow exits the bottom-right "Y" node.
**Diagram 2 (Top-Right):**
* Similar structure to Diagram 1, with nodes labeled "a<sup>-1</sup>", "a", "a", and two "Y" symbols.
* The "Y" symbols are positioned closer together than in Diagram 1.
* Arrows connect the nodes, forming a network.
* One arrow exits the bottom-right "Y" node.
**Diagram 3 (Bottom):**
* A node labeled "a<sup>-1</sup>" is at the top.
* A node labeled "a" is on the left side, slightly below the top node.
* One node with the "Y" symbol is at the bottom.
* Arrows connect the nodes, forming a network.
* One arrow exits the bottom "Y" node.
**Transformations:**
* A double-headed arrow labeled "CO-ASSOC" connects Diagram 1 to Diagram 2, indicating a co-associativity transformation.
* A curved arrow labeled "R1a" connects Diagram 2 to Diagram 3, indicating a transformation rule.
### Key Observations
* The diagrams represent compositions of morphisms and their transformations.
* The "CO-ASSOC" transformation likely rearranges the order of composition.
* The "R1a" transformation likely simplifies the diagram by applying a specific rule.
* The "Y" symbol likely represents a specific type of morphism or operation.
### Interpretation
The image illustrates how different compositions of morphisms are equivalent under the "CO-ASSOC" and "R1a" transformations. This is a fundamental concept in category theory, where the focus is on the relationships between objects and morphisms rather than the specific nature of the objects themselves. The diagrams provide a visual representation of these relationships and how they can be manipulated using these transformations. The "CO-ASSOC" transformation demonstrates that the order in which morphisms are composed does not affect the overall result, while the "R1a" transformation simplifies the diagram by applying a specific rule, possibly related to an identity morphism. The "Y" symbol likely represents a specific type of morphism or operation that is relevant to these transformations.
</details>
We proved the following relation for emergent algebras: ∆ x a ( u, x ) = inv x a u . This relation appears as a computation in graphic lambda calculus.
As for the finite differences, we may proceed as this.
Definition 5.6 A graph A ∈ GRAPH , with one input and one output distinguished, is computable with respect to the group ¯ Gamma if the following graph
<details>
<summary>Image 62 Details</summary>
### Visual Description
## Diagram: Simple Diagram with Arrows and Labels
### Overview
The image is a simple diagram consisting of two vertical lines connected by two horizontal lines. Arrows indicate the direction of flow along these lines. Circles are placed at the junctions, containing labels.
### Components/Axes
* **Vertical Lines:** Two vertical lines on the left and right sides of the diagram.
* **Horizontal Lines:** Two horizontal lines connecting the vertical lines.
* **Arrows:** Arrows indicate the direction of flow along the lines. All arrows point upwards on the vertical lines and from left to right on the horizontal lines.
* **Circles:** Circles are placed at the junctions of the lines.
* Top-left circle contains the symbol "Y".
* Top-right circle contains the label "a⁻¹".
* Bottom-left circle contains the symbol "Y".
* Bottom-right circle contains the label "a".
* **Labels "A":** The letter "A" is placed on the left and right vertical lines, between the top and bottom circles.
### Detailed Analysis
* The diagram shows a flow from bottom to top.
* The flow is modified by the elements in the circles.
* The "Y" symbol appears twice on the left side.
* The labels "a" and "a⁻¹" appear on the right side.
* The labels "A" appear on both vertical lines.
### Key Observations
* The diagram seems to represent a process or transformation.
* The "Y" symbol might represent a specific operation or component.
* The labels "a" and "a⁻¹" suggest inverse operations.
* The labels "A" might represent a constant or a variable.
### Interpretation
The diagram likely represents a sequence of operations or transformations. The "Y" symbol could represent a specific function or process, while "a" and "a⁻¹" could represent an operation and its inverse. The "A" labels might represent a constant value or a variable that is being modified by the operations. The diagram could be used to illustrate a mathematical or computational process. The flow direction indicates the order in which the operations are applied.
</details>
can be transformed by the moves from graphic lambda calculus into a graph which is made by assembling:
- -graphs from EMER ( A ) ,
- -gates λ , and .
It would be interesting to mix the emergent algebra sector with the lambda calculus sector (in a sense this is already suggested in definition 5.6). At first view, it seems that the emergent algebra gates ¯ ε are operations which are added to the lambda calculus operations, the latter being more basic than the former. I think this is not the case. In [5] theorem 3.4, in the formalism of lambda-scale calculus (graphic lambda calculus is a visual variant of this), I
show on the contrary that the emergent algebra gates could be applied to lambda terms and the result is a collection, or hierarchy of lambda calculi, organized into an emergent algebra structure. This is surprising, at least for the author, because the initial goal of introducing lambda-scale calculus was to mimic lambda calculus with emergent algebra operations.
## 6 Crossings
In this section we discuss about tangle diagrams and graphic lambda calculus.
An oriented tangle is a collection of wired in 3D space, more precisely it is an embedding of a oriented one dimensional manifold in 3D space. Two tangles are the same up to topological deformation of the 3D space. An oriented tangle diagram is, visually, a projection of a tangle, in general position, on a plane. More specifically, an oriented tangle diagram is a globally planar oriented graph with 4-valent nodes which represent crossings of wires (as seen in the projection), along with supplementary information about which wire passes over the respective crossing. A locally planar tangle diagram is an oriented graph which satisfies the previous description, with the exception that it is only locally planar. Visually, a locally planar tangle diagram looks like an ordinary one, excepting that there may be crossings of edges of the graph which are not tangle crossings (i.e. nodes of the graph).
The purpose of this section is to show that we can 'simulate' tangle diagrams with graphic lambda calculus. This can be expressed more precisely in two ways. The first way is that we can define 'crossing macros' in graphic lambda calculus, which are certain graphs which play the role of crossings in a tangle diagram (i.e. we can express the Reidemeister moves, described further, as compositions of moves from graphic lambda calculus between such graphs). The second way is to say that to any tangle diagram we can associate a graph in GRAPH such that to any Reidemeister move is associated a certain composition of moves from graphic lambda calculus.
Meredith ad Snyder [17] achieve this goal with the pi-calculus instead of graphic lambda calculus. Kauffman, in the second part of [14], associates tangle diagrams to combinators and writes about 'knotlogic'.
Oriented Reidemeister moves. Two tangles are the same, up to topological equivalence, if and only if any tangle diagram of one tangle can be transformed by a finite sequence of Reidemeister moves into a tangle diagram of the second tangle. The oriented Reidemeister moves are the following (I shall use the same names as Polyak [19], but with the letter Ω replaced by the letter R ):
- -four oriented Reidemeister moves of type 1:
- -four oriented Reidemeister moves of type 2:
<details>
<summary>Image 63 Details</summary>
### Visual Description
## Diagram: Reidemeister Move 1
### Overview
The image depicts the Reidemeister move of type 1 (R1). It shows four diagrams, each representing a transformation of a strand with a twist. The transformations are labeled R1a, R1b, R1c, and R1d, with double-headed arrows indicating the reversibility of each move.
### Components/Axes
* **Strands:** Each diagram features a strand with an arrow indicating its orientation.
* **Twists/Loops:** Some diagrams include a twist or loop in the strand.
* **Arrows:** Double-headed arrows indicate the reversibility of the moves.
* **Labels:** R1a, R1b, R1c, R1d.
### Detailed Analysis
* **Top Row:**
* **Left:** A strand with a loop. An arrow indicates the strand's orientation.
* **Arrow (R1a):** A double-headed arrow labeled "R1a" points to the right.
* **Middle:** A straight strand with an arrow pointing upwards.
* **Arrow (R1b):** A double-headed arrow labeled "R1b" points to the left.
* **Right:** A strand with a loop. An arrow indicates the strand's orientation.
* **Bottom Row:**
* **Left:** A strand with a loop. An arrow indicates the strand's orientation.
* **Arrow (R1c):** A double-headed arrow labeled "R1c" points to the right.
* **Middle:** A straight strand with an arrow pointing upwards.
* **Arrow (R1d):** A double-headed arrow labeled "R1d" points to the left.
* **Right:** A strand with a loop. An arrow indicates the strand's orientation.
### Key Observations
* R1a and R1b show the removal of a twist from a strand.
* R1c and R1d show the removal of a twist from a strand.
* The arrows indicate that the moves are reversible.
### Interpretation
The diagram illustrates the Reidemeister move of type 1, which involves adding or removing a twist in a strand. The moves are fundamental in knot theory, as they demonstrate how to transform one knot diagram into another without changing the underlying knot. The reversibility of the moves is crucial, as it allows for transformations in either direction. The diagram demonstrates the equivalence between a strand with a twist and a straight strand, highlighting the topological invariance of knots under these moves.
</details>
<details>
<summary>Image 64 Details</summary>
### Visual Description
## Diagram: Reidemeister Move 2
### Overview
The image depicts the Reidemeister move of type 2 (R2), showing four variations (R2a, R2b, R2c, R2d) of this move. Each variation illustrates the equivalence between a knot diagram with two crossings and a diagram with two parallel strands. The arrows on the strands indicate the orientation.
### Components/Axes
* **Strands:** Represented by curved lines with arrows indicating orientation.
* **Crossings:** Points where strands intersect.
* **Arrows:** Indicate the direction of the strands.
* **Labels:** R2a, R2b, R2c, R2d, each associated with a specific variation of the move.
* **Double-headed Arrows:** Indicate the equivalence between the diagrams on either side.
### Detailed Analysis
The image is divided into two rows, each containing two variations of the Reidemeister move 2.
**Top Row:**
* **R2a:** A knot diagram with two crossings on the left is equivalent to two parallel strands on the right. The double-headed arrow labeled "R2a" connects the two diagrams.
* **R2b:** Two parallel strands on the left are equivalent to a knot diagram with two crossings on the right. The double-headed arrow labeled "R2b" connects the two diagrams.
**Bottom Row:**
* **R2c:** A knot diagram with two crossings on the left is equivalent to two parallel strands on the right. The double-headed arrow labeled "R2c" connects the two diagrams.
* **R2d:** Two parallel strands on the left are equivalent to a knot diagram with two crossings on the right. The double-headed arrow labeled "R2d" connects the two diagrams.
In each case, the arrows on the strands indicate the orientation. The crossings in the knot diagrams are oriented such that one strand passes over the other.
### Key Observations
* The Reidemeister move 2 (R2) demonstrates the equivalence between a knot diagram with two crossings and a diagram with two parallel strands.
* The variations R2a and R2b are mirror images of each other, as are R2c and R2d.
* The arrows on the strands indicate the orientation, which is preserved during the move.
### Interpretation
The Reidemeister moves are a set of local moves that can be applied to a knot diagram without changing the knot itself. The Reidemeister move 2 (R2) is one of these moves, and it demonstrates the equivalence between a knot diagram with two crossings and a diagram with two parallel strands. This move is important because it allows us to simplify knot diagrams and to prove that two knot diagrams represent the same knot. The variations R2a, R2b, R2c, and R2d show different orientations of the strands, but the underlying principle remains the same.
</details>
-eight oriented Reidemeister moves of type 3:
<details>
<summary>Image 65 Details</summary>
### Visual Description
## Diagram: Reidemeister Move Type 3
### Overview
The image depicts eight variations of the Reidemeister move of type 3 (R3). Each variation shows two topologically equivalent knot diagrams, connected by a blue double-headed arrow labeled "R3[letter]". The diagrams consist of three line segments with arrows indicating direction, representing strands of a knot. The diagrams on either side of the arrow are related by a local rearrangement of the strands.
### Components/Axes
* **Knot Diagrams:** Each diagram consists of three line segments, each with an arrow indicating direction. The line segments intersect, creating over/under crossings.
* **Arrows:** Blue double-headed arrows connect pairs of diagrams, labeled R3a, R3b, R3c, R3d, R3e, R3f, R3g, and R3h.
* **Labels:** Each arrow is labeled with "R3" followed by a lowercase letter (a through h).
### Detailed Analysis
The image is organized into a 4x2 grid of diagrams. Each row contains two pairs of diagrams connected by a blue arrow.
* **R3a:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing over the intersection of the other two.
* **R3b:** The diagram on the left shows a horizontal line segment with an arrow pointing right. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing under the intersection of the other two.
* **R3c:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing over the intersection of the other two.
* **R3d:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing under the intersection of the other two.
* **R3e:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing over the intersection of the other two.
* **R3f:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing under the intersection of the other two.
* **R3g:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing over the intersection of the other two.
* **R3h:** The diagram on the left shows a horizontal line segment with an arrow pointing left. Two other line segments intersect it. The diagram on the right shows the horizontal line segment passing under the intersection of the other two.
### Key Observations
* Each pair of diagrams represents a Reidemeister move of type 3.
* The diagrams are related by a local rearrangement of the strands.
* The arrows indicate the direction of the move.
* The labels identify each variation of the move.
### Interpretation
The image illustrates the Reidemeister move of type 3, which is a fundamental concept in knot theory. This move states that two knot diagrams are equivalent if they can be transformed into each other by a sequence of Reidemeister moves. The image shows eight different variations of this move, demonstrating how the strands of a knot can be rearranged without changing the knot's topological properties. The arrows indicate the direction of the move, and the labels identify each variation. These moves are crucial for proving that two knots are equivalent or distinct.
</details>
Crossings from emergent algebras. In section 5, example 7, it is mentioned that there is a connection between tangle diagrams and emergent algebras, via the notion of a quandle. Quandles are self-distributive idempotent quasigroups, which were invented as decorations of the arrows of a tangle diagram, which are invariant with respect to the Reidemeister moves.
Let us define the emergent algebra crossing macros. (We can choose to neglect the ε decorations of the crossings, or, on the contrary, we can choose to do like in definition 5.5 of the emergent algebra sector, namely to add a set A to the group Γ and use even more nuanced decorations for the crossings.)
<details>
<summary>Image 66 Details</summary>
### Visual Description
## Diagram: Knot Theory Equivalence
### Overview
The image presents two diagrams illustrating equivalences in knot theory. Each diagram shows a transformation from a representation involving vertices and edges to a simplified crossing representation. Arrows indicate the direction of the strands.
### Components/Axes
* **Diagram 1 (Top Row):**
* Left Side: Two horizontal strands enter from the left. The top strand connects to a vertex labeled "Y" inside a circle. The bottom strand connects to a vertex labeled "ε" inside a circle. A vertical edge connects the "Y" vertex to the "ε" vertex, with an arrow pointing downwards. The strands exit to the right, with the top strand crossing over the bottom strand.
* Middle: "≡" symbol indicating equivalence.
* Right Side: Two strands cross each other. The top strand crosses over the bottom strand. The crossing is labeled "ε". Arrows indicate the direction of the strands.
* **Diagram 2 (Bottom Row):**
* Left Side: Two horizontal strands enter from the left. The top strand crosses over the bottom strand. The top strand connects to a vertex labeled "Y" inside a circle. The bottom strand connects to a vertex labeled "ε̄" inside a circle. A vertical edge connects the "Y" vertex to the "ε̄" vertex, with an arrow pointing downwards. The strands exit to the right.
* Middle: "≡" symbol indicating equivalence.
* Right Side: Two strands cross each other. The top strand crosses under the bottom strand. The crossing is labeled "ε". Arrows indicate the direction of the strands.
### Detailed Analysis
* **Diagram 1 (Top Row):**
* The left side shows a more complex representation with vertices and edges. The "Y" vertex likely represents a splitting or joining of strands, while the "ε" vertex represents a specific type of crossing.
* The right side shows the equivalent simplified crossing representation. The "ε" label indicates the type of crossing.
* **Diagram 2 (Bottom Row):**
* The left side again shows a complex representation with vertices and edges. The "ε̄" vertex likely represents the inverse of the "ε" crossing.
* The right side shows the equivalent simplified crossing representation. The "ε" label indicates the type of crossing.
### Key Observations
* The diagrams illustrate how complex representations of knots can be simplified to crossing representations.
* The "Y" vertex appears to be a standard component in these diagrams.
* The "ε" and "ε̄" labels likely represent different types of crossings or operations.
### Interpretation
The diagrams demonstrate equivalences between different representations of knots. The left side of each diagram shows a more complex representation involving vertices and edges, while the right side shows a simplified crossing representation. The "≡" symbol indicates that these two representations are equivalent. The "ε" and "ε̄" labels likely represent different types of crossings or operations, and the diagrams show how these operations can be simplified to basic crossings. The "Y" vertex likely represents a splitting or joining of strands, which is a common operation in knot theory. The diagrams suggest that complex knot diagrams can be simplified to a series of crossings, which is a fundamental concept in knot theory.
</details>
In [6], sections 3-6 are dedicated to the use of these crossings for exploring emergent algebras and spaces with dilations. All constructions and reasonings from there can be put into the graphic lambda calculus formalism. Here I shall explain only some introductory facts.
Let us associate to any locally planar tangle diagram T a graph in [ T ] ∈ GRAPH , called the translation of T , which is obtained by replacing the crossings with the emergent crossing macros (for a fixed ε ). Also, to any Reidemeister move we associate it's translation in graphic lambda calculus, consisting in a local move between the translations of the LHS and RHS tangles which appear in the respective move. (Note: these translations are not added to the moves which define graphic lambda calculus.)
Theorem 6.1 The translations of all oriented Reidemeister moves of type 1 and 2 can be realized as sequences of the following moves from graphic lambda calculus: emergent algebra moves (R1a, R1b, R2, ext2), fan-out moves (i.e. CO-COMM, CO-ASSOC, global FANOUT) and pruning moves. More precisely the translations of the Reidemeister moves R1a, R1b are, respectively, the graphic lambda calculus moves R1a, R1b, modulo fan-out moves. Moreover, all translations of Reidemeister moves of type 2 can be expressed in graphic lambda calculus with the move R2, fan-out and pruning moves.
The proof is left to the interested reader, see however section 3.4 [6].
The fact that the Reidemeister moves of type 3 are not true for (the algebraic version of) the emergent algebras, i.e. that the translations of those cannot be expressed as a sequence of moves from graphic lambda calculus, is a feature of the formalism and not a weakness. This is explained in detail in sections 5, 6 [6], but unfortunately at the moment of the writing that article the graphic lambda calculus was not available. It is an interesting goal the one of expressing the constructions from the mentioned sections as statements about the computability in the sense of definition 5.6 of the translations of certain tangle diagrams.
As a justification for this point of view, let us remark that all tangle diagrams which appear in the Reidemeister moves of type 3 have translations which are related to the approximate difference or approximate sum graphs from definition 5.4. For example, let's take the translation of the graph from the RHS of the move R3d and call it D . This graph has three inputs and three outputs. Let's then consider a graph formed by grafting three graphs A , B , C at the inputs of D , such that A , B , C are not otherwise connected. Then we can perform the following sequence of moves.
<details>
<summary>Image 67 Details</summary>
### Visual Description
## Diagram: Knot Theory Transformations
### Overview
The image presents a series of diagrams illustrating transformations in knot theory. It shows how a basic knot configuration can be represented and manipulated using diagrammatic representations involving vertices, edges, and specific operators. The transformations are labeled with terms like "CO-ASSOC" and "GLOBAL FAN-OUT," indicating different types of algebraic manipulations.
### Components/Axes
* **Diagrams:** Four separate diagrams arranged in a 2x2 grid.
* **Lines/Edges:** Represent strands of the knot, with arrows indicating direction.
* **Vertices:** Represented by circles, some containing the symbol "ε" or "Y".
* **Labels:** Letters A, B, and C, and numbers 1, 2, and 3, labeling the strands.
* **Operators:** "CO-ASSOC" and "GLOBAL FAN-OUT" indicate transformations between diagrams.
* **Equality:** The "≡" symbol indicates equivalence between the initial knot diagram and its first transformation.
### Detailed Analysis
**Top-Left Diagram:**
* A basic knot diagram with three strands labeled A, B, and C.
* Strand B crosses over strand A, and strand C crosses under strand A.
* Strands are also labeled with numbers 1, 2, and 3.
**Top-Right Diagram:**
* Represents the first transformation of the knot diagram.
* The crossing points are replaced with vertices containing "Y" symbols.
* Additional vertices containing "ε" symbols are introduced.
* The strands are still labeled A, B, and C, and numbered 1, 2, and 3.
**Bottom-Left Diagram:**
* Represents a further transformation of the knot diagram.
* The diagram has been rearranged, and the vertices are connected differently.
* The strands are still labeled A, B, and C, and numbered 1, 2, and 3.
**Bottom-Right Diagram:**
* Represents the final transformation of the knot diagram.
* The diagram has been further rearranged, forming a more symmetrical structure.
* The strands are still labeled A, B, and C, and numbered 1, 2, and 3.
**Operators:**
* "CO-ASSOC": A double-headed arrow between the top-right and bottom-right diagrams, indicating a co-associativity transformation.
* "GLOBAL FAN-OUT": A double-headed arrow between the bottom-left and bottom-right diagrams, indicating a global fan-out transformation.
### Key Observations
* The diagrams illustrate how a knot can be represented and manipulated using algebraic transformations.
* The vertices containing "ε" and "Y" symbols likely represent specific operators in the algebraic representation of the knot.
* The "CO-ASSOC" and "GLOBAL FAN-OUT" operators indicate different types of algebraic manipulations.
* The labels A, B, C, 1, 2, and 3 are consistently maintained throughout the transformations, indicating the preservation of strand identity.
### Interpretation
The image demonstrates a series of transformations applied to a knot diagram, likely within the context of knot theory or related mathematical fields. The transformations, labeled "CO-ASSOC" and "GLOBAL FAN-OUT," suggest algebraic manipulations that preserve the fundamental properties of the knot while altering its diagrammatic representation. The use of vertices with "ε" and "Y" symbols hints at a specific algebraic formalism being employed. The overall process illustrates how complex knot structures can be analyzed and simplified through diagrammatic and algebraic techniques.
</details>
The graph from the left lower side is formed by an approximate difference, a ¯ ε gate and several Υ gates. Therefore, if A , B , C are computable in the sense of definition 5.4 then the initial graph (the translation of the LHS of R3d with A , B , C grafted at the inputs) is computable too.
Graphic beta move as braiding. Let us now construct crossings, in the sense previously explained, from gates coming from lambda calculus.
<details>
<summary>Image 68 Details</summary>
### Visual Description
## Diagram: Diagram of Knot Equivalences
### Overview
The image presents two diagrams illustrating knot equivalences. Each diagram consists of two parts separated by an "equals" sign (represented by three horizontal lines). The left side of each diagram shows a configuration with labeled nodes and connecting lines with arrows, while the right side shows a simplified knot diagram.
### Components/Axes
* **Nodes:** Circular nodes labeled with "λ" or a three-pronged symbol.
* **Lines:** Lines connecting nodes and forming knot diagrams, with arrows indicating direction.
* **Equals Sign:** Represented by three horizontal lines, indicating equivalence between the two sides of each diagram.
### Detailed Analysis
**Top Diagram:**
* **Left Side:**
* Two horizontal lines enter from the left.
* The top line connects to a circular node labeled "λ".
* The bottom line connects to a circular node with a three-pronged symbol inside.
* A vertical line connects the "λ" node to the three-pronged node.
* The "λ" node has an outgoing line that curves to the right and crosses over the outgoing line from the three-pronged node.
* Arrows indicate the direction of flow along the lines.
* **Right Side:**
* A simplified knot diagram where the top line crosses over the bottom line.
* Arrows indicate the direction of flow along the lines.
**Bottom Diagram:**
* **Left Side:**
* Two horizontal lines enter from the left.
* The top line crosses over the bottom line.
* The bottom line connects to a circular node labeled "λ".
* The top line connects to a circular node with a three-pronged symbol inside.
* A vertical line connects the "λ" node to the three-pronged node.
* Arrows indicate the direction of flow along the lines.
* **Right Side:**
* A simplified knot diagram where the top line crosses under the bottom line.
* Arrows indicate the direction of flow along the lines.
### Key Observations
* The diagrams illustrate how certain configurations of nodes and lines can be simplified into basic knot crossings.
* The "λ" and three-pronged nodes seem to represent specific operations or transformations in the knot diagram.
* The direction of the arrows is crucial for understanding the flow and transformation in each diagram.
### Interpretation
The diagrams likely represent a set of rules or equivalences in knot theory or a related field. The "λ" and three-pronged nodes could represent specific mathematical operations or transformations that, when applied to a knot diagram, result in a simplified or equivalent form. The diagrams suggest that these operations can be used to manipulate and simplify complex knot diagrams into more basic crossings. The specific meaning of "λ" and the three-pronged symbol would require additional context from the source material.
</details>
As previously, we define translations of (locally planar) tangle diagrams into graphs in GRAPH . The class of locally planar tangle diagrams is out in a one-to one correspondence with a class of graphs in GRAPH , let us call this class λ -TANGLE .
We could proceed in the inverse direction, namely consider the class of graphs λ -TANGLE , along with the moves: graphic beta move and elimination of loops. Then we make the (inverse) translation of graphs in λ -TANGLE into locally planar tangle diagrams and the (inverse) translation of the graphic beta move and the elimination of loops. The following proposition explains what we obtain.
Proposition 6.2 The class of graphs λ -TANGLE is closed with respect to the application of the graphic beta move and of the elimination of loops. The translations of the graphic beta and elimination of loops moves are the following SPLICE 1, 2 (translation of the graphic beta move) and LOOP 1, 2 (translation of the elimination of loops) moves.
Proof. The proposition becomes obvious if we find the translation of the graphic beta move. There is one translation for each crossing. (Likewise, there are two translations for elimination of loops, depending on the orientation of the loop which is added/erased.)
<details>
<summary>Image 69 Details</summary>
### Visual Description
## Diagram: Splices and Loops
### Overview
The image presents a diagram illustrating two types of operations: splices and loops, applied to strands and tangle diagrams, respectively. Each operation is depicted with a "before" and "after" state, connected by a double-headed arrow indicating the transformation.
### Components/Axes
* **Splice 1:** Shows two crossing strands being spliced into two separate strands.
* **Splice 2:** Shows two crossing strands with arrows being spliced into two separate strands with arrows.
* **Loop 1:** Shows a "TANGLE DIAGRAM" being transformed into another "TANGLE DIAGRAM" with an added loop.
* **Loop 2:** Shows a "TANGLE DIAGRAM" being transformed into another "TANGLE DIAGRAM" with an added loop.
* **Double-Headed Arrows:** Indicate the transformation or operation being performed.
### Detailed Analysis
**Splice 1:**
* **Before:** Two strands cross each other.
* **Transformation:** Indicated by a double-headed arrow labeled "SPLICE 1".
* **After:** The two strands are separated, no longer crossing.
**Splice 2:**
* **Before:** Two strands cross each other, with arrows indicating direction.
* **Transformation:** Indicated by a double-headed arrow labeled "SPLICE 2".
* **After:** The two strands are separated, each with an arrow indicating direction.
**Loop 1:**
* **Before:** A shape labeled "TANGLE DIAGRAM".
* **Transformation:** Indicated by a double-headed arrow labeled "LOOP 1".
* **After:** A shape labeled "TANGLE DIAGRAM" with a loop attached to it. The loop has an arrow indicating direction.
**Loop 2:**
* **Before:** A shape labeled "TANGLE DIAGRAM".
* **Transformation:** Indicated by a double-headed arrow labeled "LOOP 2".
* **After:** A shape labeled "TANGLE DIAGRAM" with a loop attached to it. The loop has an arrow indicating direction.
### Key Observations
* The "Splice" operations involve untangling crossing strands.
* The "Loop" operations involve adding a loop to a tangle diagram.
* The arrows on the strands in "Splice 2" and on the loops in "Loop 1" and "Loop 2" indicate directionality.
### Interpretation
The diagram illustrates fundamental operations in knot theory or tangle theory. "Splice" operations simplify crossings, while "Loop" operations add complexity by introducing closed loops. These operations are likely used to manipulate and analyze the properties of knots and tangles. The diagram provides a visual representation of these transformations, aiding in understanding their effects on the structure of the diagrams.
</details>
<details>
<summary>Image 70 Details</summary>
### Visual Description
## Diagram: Splice Operations
### Overview
The image illustrates two splice operations (Splice 1 and Splice 2) using diagrammatic representations. Each operation shows an equivalence between a complex network of lines and nodes and a simpler representation involving crossing lines. The operations are linked by a transformation labeled "β".
### Components/Axes
* **Nodes:** Circular nodes with internal symbols (λ in the top node, a three-pronged symbol in the bottom node).
* **Lines:** Lines with arrows indicating direction.
* **Equivalence Symbol:** "≡" (three horizontal lines).
* **Transformation Arrow:** Curved arrow labeled "β".
* **Splice Labels:** "SPLICE 1" and "SPLICE 2" with curved arrows.
### Detailed Analysis
**Splice 1 (Top Half):**
1. **Left Side:** A complex network of lines. Two lines enter a node containing "λ" at the top. A line exits this node and connects to a node containing a three-pronged symbol. Two lines exit the three-pronged node. The top line crosses over the bottom line.
2. **Equivalence:** The complex network is equivalent to a simple crossing of two lines.
3. **Transformation:** A curved arrow labeled "β" points downwards from the complex network to two parallel lines with arrows indicating direction.
4. **Result:** The crossing of lines is equivalent to two parallel lines with arrows indicating direction.
5. **Splice Label:** A curved arrow labeled "SPLICE 1" points downwards from the crossing of lines to two parallel lines with arrows indicating direction.
**Splice 2 (Bottom Half):**
1. **Left Side:** A complex network of lines. Two lines enter a node containing "λ" at the top. A line exits this node and connects to a node containing a three-pronged symbol. Two lines exit the three-pronged node. The bottom line crosses over the top line.
2. **Equivalence:** The complex network is equivalent to a simple crossing of two lines.
3. **Transformation:** A curved arrow labeled "β" points downwards from the complex network to two parallel lines with arrows indicating direction.
4. **Result:** The crossing of lines is equivalent to two parallel lines with arrows indicating direction.
5. **Splice Label:** A curved arrow labeled "SPLICE 2" points downwards from the crossing of lines to two parallel lines with arrows indicating direction.
### Key Observations
* Both Splice 1 and Splice 2 involve a transformation from a complex network to a simpler crossing of lines.
* The transformation "β" simplifies the complex network to parallel lines.
* The only difference between Splice 1 and Splice 2 is the order in which the lines cross (top over bottom vs. bottom over top).
### Interpretation
The diagram illustrates how complex network structures can be simplified through splice operations. The "β" transformation represents a key step in this simplification process, reducing the network to parallel lines. The difference between Splice 1 and Splice 2 highlights how the order of line crossings can be significant in these operations. The diagram likely represents a step in a larger process of network simplification or manipulation, possibly within the context of theoretical physics or mathematics.
</details>
The following theorem clarifies which are the oriented Reidemeister moves which can be expressed as sequences of graphic lambda calculus moves applied to graphs in λ -TANGLE . Among these moves, some are more powerful than others, as witnessed by the following
Theorem 6.3 All the translations of the oriented Reidemeister move into moves between graphs in λ -TANGLE , excepting R2c, R2d, R3a, R3h, can be realized as sequences of graphic beta moves and elimination of loops. Moreover, the translations of moves R2c, R2d, R3a, R3h are equivalent up to graphic beta moves and elimination of loops (i.e. any of these moves, together with the graphic beta move and elimination of loops, generates the other moves from this list).
Proof. It is easy, but tedious, to verify that all the mentioned moves can be realized as sequences of SPLICE and LOOP moves. It is as well easy to verify that the moves R2c, R2d, R3a, R3h are equivalent up to SPLICE and LOOP moves. It is not obvious that the moves R2c, R2d, R3a, R3h can't be realized as a sequence of SPLICE and LOOP moves. In order to do this, we prove that R2d can't be generated by SPLICE and LOOP. Thanks are due to Peter Kravchuk for the idea of the proof, given in an answer to a question I asked on mathoverflow [7], where I described the moves SPLICE and LOOP.
To any locally planar tangle diagram A associate it's reduced diagram R(A), which is obtained by the following procedure: first use SPLICE 1,2 from left to right for all crossings, then use LOOP 1,2 from right to left in order to eliminate all loops which are present at this stage. Notice that:
-the order of application of the SPLICE moves does not matter, because they are applied
only once per crossing. There is a finite number of splices, equal to the number of crossings. Define the bag of splices SPLICE(A) to be the set of SPLICE moves applied.
- -The same is true for the order of eliminations of loops by LOOP 1, 2. There is a finite number of loop eliminations, because the number of loops (at this stage) cannot be bigger than the number of edges of the initial diagram. Define the bag of loops LOOP(A) to be the set of all loops which are present after all splices are done.
Let us now check that the reduced diagram does not change if one of the 4 moves is applied to the initial diagram.
Apply a SPLICE 1,2 move to the initial diagram A, from left to right, and get B. Then SPLICE(B) is what is left in the bag SPLICE(A) after taking out the respective splice. Also LOOP(B) = LOOP(A) because of the definition of bags of loops. Therefore R(A) = R(B).
Apply a SPLICE 1, 2 from right to left to A and get B. Then R(A) = R(B) by the same proof, with A, B switching places.
Apply a LOOP1, 2 from left to right to A and get B. The new loop introduced in the diagram does not participate to any crossing (therefore SPLICE(A) = SPLICE(B)), so we find it in the bag of loops of B, which is made by all the elements of LOOP(A) and this new loop. Therefore R(A) = R(B). Same goes for LOOP1, 2 applied from right to left.
Finally, remark that the reduced diagram of the LHS of the move R2d is different than the reduced diagram of the RHS of the move R2d, therefore the move R2d cannot be achieved with a sequence of splices and loops addition/elimination.
## References
- [1] A. Bella¨ ıche, The tangent space in sub-Riemannian geometry, in: Sub-Riemannian Geometry, A. Bella¨ ıche, J.-J. Risler eds., Progress in Mathematics , 144 , Birkh¨ auser, (1996), 4-78
- [2] M. Buliga, Dilatation structures I. Fundamentals, J. Gen. Lie Theory Appl. , 1 (2007), 2, 65-95. arXiv:math/0608536
- [3] M. Buliga, Emergent algebras, arXiv:0907.1520
- [4] M. Buliga, Braided spaces with dilations and sub-riemannian symmetric spaces, in: Geometry. Exploratory Workshop on Differential Geometry and its Applications, eds. D. Andrica, S. Moroianu, Cluj-Napoca 2011, 21-35, arXiv:1005.5031
- [5] M. Buliga, λ -Scale, a lambda calculus for spaces with dilations, arXiv:1205.0139
- [6] M. Buliga, Computing with space: a tangle formalism for chora and difference , arXiv:1103.6007
- [7] MBuliga, Oriented Reidemeister move R2d by splices and loop adding/erasing?, mathoverflow question (version: 2013-04-23)
- [8] W. Citrin, R. Hall, B. Zorn. Programming with visual expressions. Proceedings of the 11th International IEEE Symposium on Visual Languages, 1995, pp 294-301
- [9] M. Erwig, Abstract syntax and semantics of visual languages, Journal of Visual Languages and Computing 9 (1998), No. 5, 461-483.
- [10] R. Fenn, C. Rourke, Racks and Links in codimension two, J. Knot Theory Ramifications , 1 (1992), no. 4, 343-406
- [11] M. Gromov, Carnot-Carath´ eodory spaces seen from within, in the book: SubRiemannian Geometry, A. Bella¨ ıche, J.-J. Risler eds., Progress in Mathematics , 144 , Birkh¨ auser, (1996), 79-323.
- [12] H. Gl¨ ockner, Contractible Lie groups over local fields, Math. Z. 260 (2008), 889-904, arXiv:0704.3737
- [13] D. Joyce, A classifying invariant of knots; the knot quandle, J. Pure Appl. Alg. , 23 (1982), 37-65
- [14] L. Kauffman, Knot logic. Knots and applications, 1110, Ser. Knots Everything, 6, World Sci. Publ., River Edge, NJ, 1995
- [15] David C Keenan. To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction, 2001. http://dkeenan.com/Lambda/
- [16] J.J. Koenderink, The brain a geometry engine, Psychological Research , 52 (1990), no. 2-3, 122-127
- [17] L.G. Meredith, D.F. Snyder, Knots as processes: a new kind of invariant, arXiv:1009.2107
- [18] P. Pansu, M´ etriques de Carnot-Carath´ eodory et quasi-isom´ etries des espaces sym´ etriques de rang un, Ann. of Math., (2) 129 , (1989), 1-60.
- [19] M. Polyak, Minimal generating sets of Reidemeister moves, arXiv:0908.3127
- [20] E. Siebert, Contractive automorphisms on locally compact groups, Math. Z. 191 1986, Issue 1, pp 73-90.
- [21] D.P. Thurston, The algebra of knotted trivalent graphs and Turaevs shadow world arXiv:math/0311458