3 ms·

Tree Calculus

21 points by MelonUsk 24d ago

MelonUsk 24d ago
Their website: https://treecalcul.us https://treecalcul.us By the way, unary and binary trees are probably the most minimal way to generate the whole computational universe
- xelxebar 19d ago
  Surprisingly, there are combinatorial systems with just a single combinator[0]. Also, NAND along with a single axiom[0] can reproduce all of propositional calculus. By Curry-Howard-Labek, these are related facts and suggest that a universal tree likely exists in the tree calculus. [0]:https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot [1]:https://en.wikipedia.org/wiki/Nicod's_axiom https://en.wikipedia.org/wiki/Nicod's_axiom
- mathisfun123 19d ago
  > unary wtf is a unary tree? isn't that a list?
  - MelonUsk 19d ago
    Unary tree is a skewed binary tree It’s like a line with knots ;-) By itself a unary tree can encode a single number - you just count the knots
Suhinnall27 19d ago
[flagged]
peter_d_sherman 19d ago
>"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 https://en.wikipedia.org/wiki/One-instruction_set_computer
- steego 19d ago
  Great notes! I think it’s also worth noting that Barry Jay has a particularly strong vantage point for unearthing this particular foundational candidate. First, his advisor was Joachim Lambek, who’s responsible for adding Category Theory in the Curry-Howard-Lambek correspondence. If one looks at Barry’s body of work over his lifetime, it’s no surprise it would culminate into an elegantly beautiful system capable of self-reflection. I think his 2025 PEPM paper did a great job explaining the ideas to a regular programmer / wannabe academic like myself: https://github.com/barry-jay-personal/typed_tree_calculus/blob/main/typed_program_analysis.pdf https://github.com/barry-jay-personal/typed_tree_calculus/bl...
  - peter_d_sherman 18d ago
    >Great notes! Thank you! >I think it’s also worth noting that Barry Jay has a particularly strong vantage point for unearthing this particular foundational candidate. First, his advisor was Joachim Lambek, who’s responsible for adding Category Theory in the Curry-Howard-Lambek correspondence. Curry-Howard-Lambek correspondence is a very important point, I'm glad you brought it up! >If one looks at Barry’s body of work over his lifetime, it’s no surprise it would culminate into an elegantly beautiful system capable of self-reflection. No, it's not surprising indeed! >I think his 2025 PEPM paper did a great job explaining the ideas to a regular programmer / wannabe academic like myself: https://github.com/barry-jay-personal/typed_tree_calculus/blob/main/typed_program_analysis.pdf https://github.com/barry-jay-personal/typed_tree_calculus/bl... Excellent link! Random thought: From the paper: "The operator [Triangle] (pronounced "node") is a ternary operator)..." I wonder if Tree Calculus (and/or binary trees in general!) could be related to, and/or applied to the Ternary Tau and/or the Balanced Phinary number systems: https://neuraloutlet.wordpress.com/tag/ternary-tau-system/ https://neuraloutlet.wordpress.com/tag/ternary-tau-system/ https://en.wikipedia.org/wiki/Balanced_ternary https://en.wikipedia.org/wiki/Balanced_ternary
- peter_d_sherman 18d ago
  Addendum: "Tromp Diagrams" (aka "Lambda Diagrams") are potentially related to Tree Calculus, and should be added to the list above, at the very least as a visualization tool for Lambda Calculus, and potentially as an additional visualization tool for other compatible systems: https://tromp.github.io/cl/diagrams.html https://tromp.github.io/cl/diagrams.html Related Video: 2swap - "What is PLUS times PLUS?" https://www.youtube.com/watch?v=RcVA8Nj6HEo https://www.youtube.com/watch?v=RcVA8Nj6HEo (An excellent example of how Lambda/Tromp Diagrams can be used to visualize Mathematics (i.e. application of a function to another function, recursive functions, etc., as line drawings with horizontal and vertical lines -- which almost look like Sanskrit...))
orangea 19d ago
has tree calculus been used to prove something interesting about something that is not tree calculus?
- MelonUsk 19d ago
  It basically has 3 rules: the first two are K (“deletion”) and S combinator (“copying/spreading”), the 3rd is F: That is like “selection/choosing” of the 1, 2 or 3 node structure to operate on, if I understood correctly: / or \ (think 0 or 1) 2 nodes: / \ Or \ / 3 nodes: \ /\ Or / /\ The whole program in binary calculus is not just a mess of zeros and ones in a binary form but has structure, so you can visually see lists, iteration, recursion, etc You can theoretically code GTA-6 or the universe very much like ours using a binary tree ;-) This language also has types and as far as I understood it was already implemented in itself - the whole parser/compiler fits on a book page Better to hear from the author himself: https://youtu.be/aer5fH-OxeE https://youtu.be/aer5fH-OxeE

21 points by MelonUsk 24d ago

Their website: https://treecalcul.us https://treecalcul.us By the way, unary and binary trees are probably the most minimal way to generate the whole computational universe

xelxebar 19d ago
Surprisingly, there are combinatorial systems with just a single combinator[0]. Also, NAND along with a single axiom[0] can reproduce all of propositional calculus. By Curry-Howard-Labek, these are related facts and suggest that a universal tree likely exists in the tree calculus. [0]:https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot [1]:https://en.wikipedia.org/wiki/Nicod's_axiom https://en.wikipedia.org/wiki/Nicod's_axiom
mathisfun123 19d ago
> unary wtf is a unary tree? isn't that a list?
- MelonUsk 19d ago
  Unary tree is a skewed binary tree It’s like a line with knots ;-) By itself a unary tree can encode a single number - you just count the knots

Suhinnall27 19d ago

[flagged]

peter_d_sherman 19d ago

>"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 https://en.wikipedia.org/wiki/One-instruction_set_computer

steego 19d ago
Great notes! I think it’s also worth noting that Barry Jay has a particularly strong vantage point for unearthing this particular foundational candidate. First, his advisor was Joachim Lambek, who’s responsible for adding Category Theory in the Curry-Howard-Lambek correspondence. If one looks at Barry’s body of work over his lifetime, it’s no surprise it would culminate into an elegantly beautiful system capable of self-reflection. I think his 2025 PEPM paper did a great job explaining the ideas to a regular programmer / wannabe academic like myself: https://github.com/barry-jay-personal/typed_tree_calculus/blob/main/typed_program_analysis.pdf https://github.com/barry-jay-personal/typed_tree_calculus/bl...
- peter_d_sherman 18d ago
  >Great notes! Thank you! >I think it’s also worth noting that Barry Jay has a particularly strong vantage point for unearthing this particular foundational candidate. First, his advisor was Joachim Lambek, who’s responsible for adding Category Theory in the Curry-Howard-Lambek correspondence. Curry-Howard-Lambek correspondence is a very important point, I'm glad you brought it up! >If one looks at Barry’s body of work over his lifetime, it’s no surprise it would culminate into an elegantly beautiful system capable of self-reflection. No, it's not surprising indeed! >I think his 2025 PEPM paper did a great job explaining the ideas to a regular programmer / wannabe academic like myself: https://github.com/barry-jay-personal/typed_tree_calculus/blob/main/typed_program_analysis.pdf https://github.com/barry-jay-personal/typed_tree_calculus/bl... Excellent link! Random thought: From the paper: "The operator [Triangle] (pronounced "node") is a ternary operator)..." I wonder if Tree Calculus (and/or binary trees in general!) could be related to, and/or applied to the Ternary Tau and/or the Balanced Phinary number systems: https://neuraloutlet.wordpress.com/tag/ternary-tau-system/ https://neuraloutlet.wordpress.com/tag/ternary-tau-system/ https://en.wikipedia.org/wiki/Balanced_ternary https://en.wikipedia.org/wiki/Balanced_ternary
peter_d_sherman 18d ago
Addendum: "Tromp Diagrams" (aka "Lambda Diagrams") are potentially related to Tree Calculus, and should be added to the list above, at the very least as a visualization tool for Lambda Calculus, and potentially as an additional visualization tool for other compatible systems: https://tromp.github.io/cl/diagrams.html https://tromp.github.io/cl/diagrams.html Related Video: 2swap - "What is PLUS times PLUS?" https://www.youtube.com/watch?v=RcVA8Nj6HEo https://www.youtube.com/watch?v=RcVA8Nj6HEo (An excellent example of how Lambda/Tromp Diagrams can be used to visualize Mathematics (i.e. application of a function to another function, recursive functions, etc., as line drawings with horizontal and vertical lines -- which almost look like Sanskrit...))

orangea 19d ago

has tree calculus been used to prove something interesting about something that is not tree calculus?

MelonUsk 19d ago
It basically has 3 rules: the first two are K (“deletion”) and S combinator (“copying/spreading”), the 3rd is F: That is like “selection/choosing” of the 1, 2 or 3 node structure to operate on, if I understood correctly: / or \ (think 0 or 1) 2 nodes: / \ Or \ / 3 nodes: \ /\ Or / /\ The whole program in binary calculus is not just a mess of zeros and ones in a binary form but has structure, so you can visually see lists, iteration, recursion, etc You can theoretically code GTA-6 or the universe very much like ours using a binary tree ;-) This language also has types and as far as I understood it was already implemented in itself - the whole parser/compiler fits on a book page Better to hear from the author himself: https://youtu.be/aer5fH-OxeE https://youtu.be/aer5fH-OxeE