Tree Calculusはラムダ計算より単純で反射的、その仕様は驚くほどコンパクト
Tree Calculusは、ラベルなし二分木と3つの縮約規則だけでTuring完全かつ反射的という計算体系。λ計算より単純で、紙とペンでも実行可能。著者は母に1時間で説明し、not true→falseの縮約を再現させた。プログラム最適化や他言語への変換など応用も広がる。
私の母はとても賢いが、λ計算や組み合わせ論理、項書き換えシステムを聞いたことがなかった。それでもTree Calculusはギリシャ文字や括弧なしで説明でき、使える。すべてが木だからだ。
HNでの議論
10- MelonUsk
彼らのウェブサイト: https://treecalcul.us
ちなみに、単項木と二項木はおそらく計算宇宙全体を生成するための最もミニマルな方法だ
- orangea
tree calculus は、tree calculus ではない何かについて興味深いことを証明するのに使われたことがあるのだろうか？
- peter_d_sherman
>「Tree calculus は、最小限でモジュール式の、チューリング完全かつ反射的な計算体系である。」
これにより、それはすべての数学の基礎の候補となる…
この領域における他の候補には、圏論（すべては「合成」と呼ばれる単一の操作に還元される）、ラムダ計算（すべては関数適用に還元される）、形式書き換えシステム（別名 記号置換 / Post 標準系 / マルコフアルゴリズム——すべては単一の操作に還元される：文字列の書き換え、つまり記号のパターンを照合して別のものに置き換えること。例えばチューリングマシンはこの空間の中に存在する…）、ホモトピー型理論（別名 HoTT：変換としてのパス。等式の言明（a = b）は静的な真理値ではなく、高次元空間に住むパス（あるいは連続的な変換）である。論理的証明、代数的操作、幾何学的変形はすべて「パス帰納法」の概念の下に統一される。二つの数学的構造が等価であることを証明することは、それらの間に連続的な変換のパスを見つけることと等価である。）などがある。
それがその一部であり、他にはチューリング完全な有限オートマトン、つまり Rule 110 などなどがある。）
ともあれ、素晴らしいリンクであり、このリストに Tree Calculus を歓迎する！
関連: https://en.wikipedia.org/wiki/One-instruction_set_computer