4 ms·

You might like "To Mock a Mockingbird" by Raymond Smullyan. It's a book of logic puzzles with a focus on combinatory logic (a model of computation related to th

• psykotic 14y ago
  As fond as I am of the Mockingbird book and Smullyan's books in general, I'd say that most of its puzzles are pure exercises in abstract symbol manipulation and not terribly enlightening. If you have some prior exposure to the SKI combinators, one big aha-moment may come from the book's exploration of several alternative axiom systems that, while preceding the SK system chronologically, are often left out of modern CS-oriented treatments of combinatory logic. Also, while I think the exercises on symbol manipulation are not very enlightening on their own, the syntactic rewriting point of view is a useful complement if your view of combinatory logic has been mostly semantic. Proving completeness in the syntactic framework becomes a matter of showing that any combinatory rewriting rule can be expressed in terms of your base combinators. This in turn can be done if your combinators allow arbitrary permutations to be expressed in addition to duplication and dropping of symbols (cf. lengthening and shortening rules in GEB). For example, K is a dropping combinator, and rather than viewing S as a substitution operator on the semantic level (as is done when translating lambda calculus to SK calculus), it can be viewed as a hybrid permutation and duplication combinator at the syntactic level. If these dual roles are split into separate combinators, you get alternative axiom systems.