From: barker Date: Sat, 18 Sep 2010 20:23:31 +0000 (-0400) Subject: (no commit message) X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=d1761bf08a977c86230b82fbd4b9da0c7b940d78 --- diff --git a/week2.mdwn b/week2.mdwn index 13fd1c89..b23d1a74 100644 --- a/week2.mdwn +++ b/week2.mdwn @@ -184,7 +184,14 @@ van Heijenoort (ed) 1967 *From Frege to Goedel, Cresswell has also developed a variable-free approach of some philosophical and linguistic interest in two books in the 1990's. -These systems are Turing complete. In other words: every computation we know how to describe can be represented in a logical system consisting of only a single primitive operation! +A final linguistic application: Steedman's Combinatory Categorial Grammar, where the "Combinatory" is +from combinatory logic (see especially his 2000 book, *The Syntactic Process*). Steedman attempts to build +a syntax/semantics interface using a small number of combinators, including T = \xy.yx, B = \fxy.f(xy), +and our friend S. Steedman used Smullyan's fanciful bird +names for the combinators, Thrush, Bluebird, and Starling. + +Many of these combinatory logics, in particular, the SKI system, +are Turing complete. In other words: every computation we know how to describe can be represented in a logical system consisting of only a single primitive operation! Here's more to read about combinatorial logic. Surely the most entertaining exposition is Smullyan's [[!wikipedia To_Mock_a_Mockingbird]].