Lucent Technologies Bell Labs
600 Mountain Avenue
Murray Hill
NJ 07974, USA
carp@colloquial.com
http://colloquial.com/carp
In this paper, we demonstrate that the multimodal categorial grammars are in fact Turing-complete in their weak generative capacity. The result follows from a straightforward reduction of generalized rewriting systems to a mixed associative and modal categorial calculus. We conclude with a discussion of a restriction to the so-caled weak Sahlqvist lexical rules, for which we can ensure decidability.
I'm contributing this paper, because j50 himself was the first person to introduce me to type-logical categorial grammars. I still clearly remember that small workshop in 1986, when a few of the folks in Edinburgh working on GPSG and CG with Mark Steedman and Ewan Klein crossed the channel for an eye-opening workshop hosted by Johan van Benthem and Herman Hendriks. Glyn Morrill and I immediately went back to Edinburgh and started rethinking our entire view of the foundation of linguistics. It took several years, but we both followed Johan into the categorial-grammar-book-writing business, and have never looked back. Thanks, Johan. You've been an inspiration.