Tree calculus: a Turing-complete language where programs are just trees
Tree calculus is a minimal, modular, Turing-complete and reflective calculus where programs and values are unlabeled binary trees. This visual introduction explains the reduction rules of triage calculus, shows how to represent data like booleans and lists, and demonstrates constructing programs such as 'not' and 'size'. The author tested the explanation on his mom, who had no prior knowledge of lambda calculus, and she successfully reduced expressions with pen and paper.
After under 1h of me explaining and sketching things with pen and paper, she successfully rendered out the reductions of 'not false → true' and 'not true → false' and understood what's going on.
- MelonUsk
Their website: https://treecalcul.us
By the way, unary and binary trees are probably the most minimal way to generate the whole computational universe
- orangea
has tree calculus been used to prove something interesting about something that is not tree calculus?
- peter_d_sherman
>"Tree calculus is a minimal, modular, Turing-complete and reflective calculus."
This makes it a candidate for the foundation of all of Mathematics...
Other candidates in this space include such things as Category Theory (everything reduces down to a single operation called a 'composition'), Lambda Calculus (everything reduces down to function application), Formal Rewriting Systems (aka Symbol Substitution / Post Canonical System / Markov Algorithm -- everything reduces to a single operation: string rewriting, matching a pattern of symbols and replacing it with another. Turing Machines, for example, exist within this space...), Homotopy Type Theory (aka HoTT: Paths as Transformations, statements of equality (a = b) are not static truth values; they are paths (or continuous transformations) living in a higher-dimensional space. Logical proofs, algebraic manipulations, and geometric deformations are all unified under the concept of "path induction." Proving that two mathematical structures are equivalent is equivalent to finding a continuous path of transformation between them.")
That's some of them, others include such things as Turing Complete Finite Automata, i.e., Rule 110, etc., etc.)
Anyway, excellent link, and we welcome Tree Calculus to this list!
Related: https://en.wikipedia.org/wiki/One-instruction_set_computer