A riemannian manifold (X,g) is a length metric space (X,d) by Hopf-Rinow thm.

• • (1935, A. Wald) problem 1 for 2-dim manifolds.
• • (1948, A.D. Alexandrov) a metric notion of (sectional) curvature + smoothness solves 2-dim manifolds.
• • (1982, A.D. Alexandrov) conjecture that the same is true for n-dim manifolds.
• • (1998, I.G. Nikolaev) proves (Alexandrov conjecture) for n-dim manifolds.

but (1996, M. Gromov) asks for a solution of

• (X,D,g) sub-riemannian if D completely non-integrable distribution and g a metric on D.
• by Hopf-Rinow (X,D,g) is a length metric space (X,d), with d the CC distance.

• • metric (Hausdorff) dimension > topological dimension
• • not Alexandrov spaces
• • tangent spaces are nilpotent (Carnot) groups, not vector spaces
• • Carnot groups have a peculiar differential calculus (Pansu derivative)

• • (1981, M. Gromov) finitely generated groups of polynomial growth same as those groups which have nilpotent subgroups of finite index
• • (1989, P. Pansu) proves Rademacher thm for Carnot groups, which implies a short proof for Margulis-Mostow rigidity
• • (2006, J.R. Lee, A. Naor) counter-example to Goemans-Linial conjecture by using the Heisenberg group as a SR space
• • (2010, E. Hrushovski) (2011, E. Breuillard, B. Green, T. Tao) Approximate groups are essentially Carnot groups

(2011, B.) solution of problem 2 which uses emergent algebras and graph rewrites.

(2009, B., 2018, B.) An emergent algebra (X, Γ, ∘, •) is:

• - a topological uniform space X, endowed with
• - a Γ-indexed family of idempotent right quasigroup operations
• - for which certain derived operations converge as the index "converges to 0"

∀ A ∈ Γ ∘ = ∘(A), • = •(A)

• (Reidemeister 1) x ∘ x = x = x • x   ∀ x ∈ X
• 
• (Reidemeister 2) e • (e ∘ x) = x = e ∘ (e • x)   ∀ e, x ∈ X
• 
• (act) (Γ, ⋅, 1) is commutative group, acts:
•    
• 
• (em) (Γ, ⋅, 1) is continuous, with an absolute 0.
  As a ∈ Γ → 0
• x ∘(a) y → x ∘(0) y = x , unif wrt x, y in compact sets
• Δ(a)(e,x,y) → Δ(0)(e,x,y) , unif wrt x, y in compact sets

Thm: Fix e ∈ X and denote x * y = Σ(0)(e,x,y). Then (X,*,e) is a conical group: continuous,

• contractive: as a ∈ Γ → 0, a ⋅ x → e, uniformly wrt x in compact set
• (Γ, ⋅, 1) scalar multiplication: a ⋅ (x * y) = (a ⋅ x) * (a ⋅ y)

• • (normed) finite dim vector space X, * = +, Γ = (0, ∞)
• • Heisenberg groups:
  • - take (H, <,>) complex Hilbert space, X = H × R
  • (x,u) * (y,v) = (x + y, u + v + (1/2) Im <x,y>)
  • - distribution D from left translate of H in X, is completely nonintegrable
  • - metric on D from Re <,>
  • - Γ = C ∖ {0}
  • a ⋅ (x,u) = (a x , ∣a∣² u )
• • or just any Carnot group

The operation * is commutative iff any of the following:

• - we can do the shuffle trick:
• 
• - rays are semigroups, uniformly
• ∀ a, b ∈ Γ, ∃ a+b ∈ Γ, (a ⋅ x) * (b ⋅ x) = (a+b) ⋅ x
• - barycentric condition: ∀ a ∈ Γ, ∃ 1-a ∈ Γ
• 

Oriented knot diagrams are a class of graphs, with the Reidemeister rewrites.

A minimal, sufficient collection of Reidemeister rewrites:

i.e. an asynchronous graph-rewrite automaton (S,R,A):

• - S is the class of graphs as before
• - R is the class of rewrites of emergent algebras
• - A is the simplest algorithm of rewrite: random

There are no points, there is no passive space, everything is shared computation on this substrate.

Problem: what can this automaton do? Can it compute?

Btw, what is computation?

(1936, A. Church) Pure λ calculus is a term rewrite system

Terms:

• variable: x, y, z, ...
• term:
  • - variable  
  • - A B where A, B terms     (application)
  • - λx.A where x var, A term     (abstraction)

Term rewrite rule:

• β-reduction: (λx.D)B → D[x=B]

What algorithm?

(1971, C.P. Wadsworth, 1990, J. Lamping) graph rewrite system

Logic is the language of a category

• - an object A is a type
• - a subobject is a proposition (predicate)
• - an arrow A → B is a term of type B containing a free variable of type A
• - operations come from universal constructions

• - typed λ calculus - cartesian closed category (internal hom, products), like Set
• - linear logic - closed symmetric monoidal category, (internal hom, tensor product) like Vect
• - quantum logic - dagger category (internal hom, tensor product, adjoint) like Hilb
• - none of the above - (no internal hom, product?, no adjoint) Conical

Untyped lambda calculus + emergent algebras

• - S: oriented fatgraphs with 3-valent L,A,FI,FO, 1-valent T
• - R: graphical β rewrite
  
  
• - R: Reidemeister rewrites
  
  
  
  
• - CO-COMM, CO-ASSOC for the FO nodes

• - S: oriented fatgraphs with 3-valent L,A,FI,FO, 1-valent T
• - R: graphical β rewrite and FAN-IN
  
  
• - R: DIST rewrites
  
  
• - R: CO-COMM, CO-ASSOC rewrites
  
  

Chemlambda v1 is a version of oriented Interaction Combinators (1990, 1997 Y. Lafont), with conflicting rewrites (so nondeterministic) and a fixed algorithm of reduction (random), i.e. an artificial chemistry.

Chemlambda v1 was initially "The chemical concrete machine", as (1992, G. Berry, G. Boudol) The chemical abstract machine.

Chemlambda v1 uses λ calculus as chemistry, related to Algorithmic Chemistry (2004, W. Fontana, L.W. Buss)

GLC and Chemlambda v1 are Turing universal as regards the rewrites.

Huge interest for decentralized computing!

Louis Kauffmann is the first programmer in chemlambda.

M.B., L.H. Kauffman, Chemlambda, universality and self-multiplication (slides) (journal copy)

I wrote chemlambda v2 in awk + d3.js

Discovered quine graphs

Viable proposal for chemical computation (2015, B. Molecular computers)

- version in python (by 4lhc)

- version in Haskell (by synergistics)

- version in js (by ishanpm)

- Lambdalife: chemlambda projects page

- kaleidoscope (kali) is an async automaton with 11 nodes.

- 6 nodes related to the anharmonic group.

- FO related to ∞, (T,FRIN, FROUT) related to 0 and 1

- and Kauffman' Arrow