The Turing Completeness of Multimodal Categorial Grammars

Bob Carpenter

Lucent Technologies Bell Labs
600 Mountain Avenue
Murray Hill
NJ 07974, USA


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.

Further Information

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.

Bibtex Entry