Tree Calculus: Turing-vollständig, reflektierend und so einfach, dass deine Mutter es lernen kann
Tree Calculus ist ein minimaler, modularer, Turing-vollständiger und reflektierender Kalkül, bei dem Programme und Werte als unbeschriftete Binärbäume dargestellt werden. Die Reduktionsregeln sind so kompakt, dass selbst jemand ohne Vorkenntnisse in λ-Kalkül oder Kombinatorik nach einer Stunde eigenständig Ausdrücke wie „not true“ reduzieren kann. Der Artikel bietet eine visuelle Einführung und zeigt, wie sich komplexe Programme allein durch Bäume konstruieren lassen.
Ich habe diese Theorie an meiner Mutter getestet. Nach weniger als einer Stunde, in der ich ihr alles mit Stift und Papier erklärte und skizzierte, hat sie erfolgreich die Reduktionen von „not false → true“ und „not true → false“ durchgeführt und verstanden, was vor sich geht.