… program, this one: How time flows: Gutenberg time vs Internet time . Before I used js only for the latest stage, written (clumsily, I admit) by other programs. Since then I wrote hapax and I modified other scripts to fit my needs, mainly, but this corrected a gap in my education 🙂

Oh btw if anybody interested to see/interact on this talk I’d like to propose: [adapted from a pdf (sigh) for my institution management, though they are in the process to reverse to the pre-internet era and they managed to nuke all mail addresses @imar.ro a domain which was rock solid since at least 20 years; that’s why I post it here]

A kaleidoscope of graph rewrite systems in topology, metric geometry and computer science

Graph rewrite systems are used in many research domains, two among many examples are Reidemeister moves in knot theory or Interaction Combinators in computer science. However, the use of graph rewrites systems is often domain dependent. Indeed, for the knot theory example we may use the Reidemeister move in order to prove that the Kauffman bracket is a knot invariant, which means that it does not change after the graph is modified by any rewrite. In the other case given as an example, Interaction Combinators are interesting because they are Turing universal: any computation can be done with IC rewrite rules and the rewrites are seen as the computational steps which modify the graphs in a significant way.

In this talk I want to explain, for a general audience, the ocurence and relations among several important graph rewrite systems. I shall start with lambda calculus and the Church-Turing thesis, then I shall describe Lafont’ Interaction Combinators [1]. After that I shall talk about graphic lambda calculus [2], about joint work with Louis Kauffman [3] on relations with knot theory. Finally I explain how I, as a mathematician, arrived to study graph rewrites systems applications in computer science, starting from emergent algebras [4] proposed in relation with sub-riemannian geometry and ending with chemlambda [5], hapax (demo page [6], presentation slides [7]) and em-convex [8] with the associated graph rewrite system [9] (short of “kaleidoscope”).

During the talk I shall use programs which are based on graph rewrites, which are free to download and play with from public repositories.

[1] Y. Lafont, Interaction Combinators, Information and Computation 137, 1, (1997), p. 69-101

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.5761&rep=rep1&type=pdf

[2] M. Buliga, Graphic lambda calculus. Complex Systems 22, 4 (2013), p. 311-360

https://www.complex-systems.com/abstracts/v22_i04_a01/

[3] M. Buliga, L.H. Kauffman, Chemlambda, Universality and Self-Multiplication, The 2019 Conference on Artificial Life 2014 NO. 26, p.490-497

https://www.mitpressjournals.org/doi/pdf/10.1162/978-0-262-32621-6-ch079

[4] M. Buliga, Emergent algebras, arXiv:0907.1520

https://arxiv.org/abs/0907.1520

[5] M. Buliga, Chemlambda, GitHub repository (2017)

https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/README.md

[6] M. Buliga, Hapax, (2019) demo page http://imar.ro/~mbuliga/hapax.html,

Github repository https://github.com/mbuliga/hapax

[7] M. Buliga, Artificial physics of artificial chemistries, slides (2019)

http://imar.ro/~mbuliga/genchem.html

[8] M. Buliga, The em-convex rewrite system, arXiv:1807.02058

https://arxiv.org/abs/1807.02058

[9] M. Buliga, Anharmonic lambda calculus, or kali (2019),

demo page https://mbuliga.github.io/kali24.html

I’d like to make this much more funny than it looks by using these js scripts. Also “kaleidoscope” is tongue-in-cheek, but that’s something only we know. Anyway kali is on the way to be finished, simplified and documented. And somehow different. For a short while, encouraged by these js scripts and similar attempts, I tried to believe that maybe, just maybe there is a purely local way to do untyped lambda, right around the corner. But it seems there isn’t, although it was fun to try again to search it. But then what to do? Maybe to be honest with the subject and say that indeed a purely local system, geometry inspired, exists, it it Turing universal, but it is not lambda calculus (although it can be guided by humans into being one, so that’s not the problem)? Maybe going back to my initial goal, which was to understand space computationally, which I do now? Yeah, I know that lambda calculus is fascinating, even more if untyped, but em is so much better!