Conversation

Interesting: Tree calculus, which is Turing complete/equivalent since it can emulate both S and K combinators.

Post by @maonu: https://mathstodon.xyz/@maonu/113625786880840164

Which links to a Tree Calculus web site, which has both an OCaml and a JavaScript implementation of the reduction rules:

https://treecalcul.us/specification/

Which mentions a book:
"Reflective Programs in Tree Calculus", by Barry Jay and Jose Vergara, 2021
"Tree calculus is seeded by a single operator, whose self-application gives rise to pow- erful reflective programs including a size program that can compute its own size, an equality program that can decide its own equality, and a self-evaluator that can evaluate itself. This is achieved without any of the usual outside machinery, such as the Gödel numbering of Turing machines, the quotation of lambda-abstractions or serialisation of programs. The resulting theory of computation is both simple and powerful: simple because it is based on three equations only; powerful because one program can query the internal structure of another, using a mix of extensional and intensional techniques"

https://www.amazon.com/Reflective-Programs-Tree-Calculus-Barry-ebook/dp/B095BPM2MF