Tree Calculus: 튜링 완전하면서 반영적인 계산법, 종이와 펜으로 배우다
Tree Calculus는 최소한의 모듈식 튜링 완전 계산법으로, 프로그램과 값을 레이블 없는 이진 트리로 표현한다. 저자는 어머니에게 1시간도 안 되어 'not true → false'와 'not false → true'의 축약을 설명했고, 어머니는 이를 성공적으로 수행했다. 이 계산법은 람다 계산법보다 단순하면서도 반영적이어서 스스로를 최적화할 수 있다. 웹사이트에서 인터랙티브 데모를 제공한다.
내 어머니는 매우 똑똑하시지만, λ-계산법이나 조합 논리, 항 재작성 시스템에 대해 들어본 적이 전혀 없으셨다. 그런데도 여전히 그렇다. 왜냐하면 tree calculus는 그리스 문자나 괄호 없이도 설명하고 사용할 수 있기 때문이다. 모든 것이 트리이기 때문이다.