In this post, following “Emergent algebras and combinatory logic (part III)“, I define the class of “computable” graphs in and then I show you how differentiability (a generalization of Pansu notion of differentiability on Carnot groups) can be seen as related to this “computability”.
I am using the notations from the last post. See also the post Combinators and zippers for the other notions which I shall use here. The tutorial on graphic lambda calculus may be consulted, if necessary.
1. The combinatory logic sector. This is the collection of graphs in denoted by which is generated by:
- untyped lambda calculus zippers,
- arrows and loops,
- the diamond,
- the termination gate,
with the operation of linking outputs to inputs,under the constraint that we get graphs with a single output, which has to be either:
- the upper side output of the diamond,
- or the upper side output of a zipper
and with the moves:
- this sector contains the untyped lambda calculus sector,
- conjecture: any graph is can be transformed into a finite collection of graphs in the untyped lambda calculus sector.
2. Emergent computable graphs. I define the sector of as the collection of graphs in which are generated by the reunion of and , with the collection of moves which belong to one of the sectors, that is all moves excepting the dual of the graphic beta move and the ext1 move.
This sector can be described as the collection of graphs in generated by:
- graphs in ,
- gate and the gates for any ,
- the approximate sum gate and the approximate difference gate , for any ,
with the operations of linking output to input arrows and with the following list of moves:
3. Computably differentiable graphs. A graph which has at least one input and one output is computably differentiable if the following graph is in
I shall explain in a future post the meaning of this definition, after writing a bit about differentiability in emergent algebras and about the Pansu differentiability.