Tree Calculusはラムダ計算より単純で反射的、その仕様は驚くほどコンパクト
Tree Calculusは、ラベルなし二分木と3つの縮約規則だけでTuring完全かつ反射的という計算体系。λ計算より単純で、紙とペンでも実行可能。著者は母に1時間で説明し、not true→falseの縮約を再現させた。プログラム最適化や他言語への変換など応用も広がる。
私の母はとても賢いが、λ計算や組み合わせ論理、項書き換えシステムを聞いたことがなかった。それでもTree Calculusはギリシャ文字や括弧なしで説明でき、使える。すべてが木だからだ。