《The-Turing-Completeness-of-Multimodal-Categorial-Grammars.pdf》由会员分享，可在线阅读，更多相关《The-Turing-Completeness-of-Multimodal-Categorial-Grammars.pdf（9页珍藏版）》请在三一文库上搜索。
1、The Turing Completeness of Multimodal Categorial Grammars Bob Carpenter May 25, 1999 Abstract 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 rewriti
2、ng 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. Contents 1Introduction2 2Multimodal Categorial Grammar2 3Turing Completeness6 4Sahlqvist Axioms and Deci
3、dability7 5Conclusion8 1 1Introduction 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
4、 calculus. It turns out that we should not be surprised that seemingly arbitrary kinds of operations can be coded in multimodal categorial grammars. In this paper, we show that any computable grammar can be coded as a multimodal catego- rial grammar. From the standpoint of formal linguistics, this o
5、pening of the computational fl oodgates might even appear to be inevitable. Simply compare the introduction of general transformations in transformational grammars Pe- ters and Ritchie 1973, metarules in phrase structure grammars Uszkoreit and Peters 1986, and lexical rules in categorial and phrase
6、structure systems Car- penter 1991, all of which have been shown to be Turing-complete. Although steps may be taken to restrict the power of these systems to ensure decidability, such moves appear rather ad hoc because of their lack of linguistic motivation. For instance, consider the restrictions a
7、gainst metarule self application Gazdar et al. 1985, or the fi nite bound placed on unary phrase structure rules (and by association, empty categories) by Kaplan and Bresnan 1982. Natural language syntax is a diffi cult matter, and no formalism has even come close to providing a universal system in
8、which all and only natural lan- guage grammars can be expressed. Perhaps even more discouraging is the fact that no grammars for particular languages have ever been developed that even come close to covering a naturally occurring range of data in a theoretically clean fashion. On the other hand, the
9、 grammar fragments that are typically proposed in formalisms such as GB, HPSG, and LFG are much better behaved computationally than the worst-case analysis would suggest.But when ob- served phenomena begin to exceed the natural coverage of a formalism, more powerful mechanisms are typically introduc
10、ed. 2Multimodal Categorial Grammar The general paradigm of multimodal categorial grammars was introduced by Moortgat 1994, following earlier multimodal developments by Hepple 1990, Morrill 1991, 1994, and Moortgat and Oehrle 1994. The fundamental idea underlying these systems is that languages allow
11、 many diff erent modes of combi- nation for linguistic expressions (which have often been called resources in the literature, following common usage in linear logic). In addition to Lambeks 1958, 1961 original modes of associative and non-associative concatenation, several additional mechanisms have
12、 been proposed. For instance, commuta- tive operations have been applied to free word-order languages Hepple 1990; Moortgat and Oehrle 1994, wrapping and infi xing have been used to deal with scoping and unbounded dependencies Moortgat 1991; Morrill 1994, 1995 and to deal with gapping and ellipsis S
13、olias 1992. In some systems, unary modes of combination have been used to deal with permuting for unbounded dependen- 2 cies Morrill 1994, islands and locality constraints Hepple 1990; Morrill 1990, 1994, for encoding syntactic features Kraak 1995, and for relaxing control in order to copy resources
14、 for parasitic gaps Morrill 1994. More recently, analyses of clitics Kraak 1995 and general word-order domains Versmissen 1996 have been proposed in even more elaborate multi-modal systems. We will provide a sequent-based proof theoretic presentation of multimodal categorial grammar. There are sever
15、al other presentations possible, including semantic ones, of the same logic Morrill 1994; Moortgat 1994. As usual, we begin with a fi nite set AtCat of atomic category symbols. We also assume a fi nite set UnMod of unary modes of combination and a fi nite set BinMod of binary modes of combination. W
16、e then defi ne the set of Cat of categories to be the least such that: AtCat Cat 2uA,3uA Cat if A Cat and u UnMod A/bB,BbA,AbB Cat if A,B Cat and b BinMod The proof theory will be presented in Belnaps 1981 display logic, a general- ization of Gentzen-style sequent proofs. The antecedents of sequents
17、 are struc- tured according to their mode of combination. The collection Ant of sequent antecedents is the least such that: Cat Ant ()u Ant if Ant and u UnMod (,)b Ant if , Ant and b BinMod The set Seq of sequents is the least such that: A Seq if Ant and A Cat The inference schemes then follow the g
18、eneral scheme of residuation for unary and binary operations Moortgat 1994. In terms of sequent rule schemes, this amounts to left and right rules for each of our binary and unary connectives. These are as follows. ID A A (A)u B3 uL 3uA B A 3uR ()a 3uA A B 2uL (2uA)u B ()u A2 uR 2uA BA C/ bL (A/bB,)
19、b C (,B)b A/ bR A/bB BA C bL (,BbA)b C (B,)b A bR BbA 3 (A,B)b C bL AbB C A B bR (,)b AbB A proof of a sequent A consists of a tree rooted at A, every local tree of which matches some inference rule, and every branch of which is terminated with an application of the identity scheme. Lambeks 1961 non
20、-associative calculus, often called NL, is given by simply taking UnMod = and BinMod = n. The rules for the product and the left and right slash then correspond to Lambeks own presentation.NL is the weakest possible logic based on residuation, thus making it the one that is most sensitive to the str
21、ucture of expressions. Lambeks 1958 associative calculus, often called L, on the other hand, can be defi ned by taking UnMod = and BinMod = a, along with the following pair of structural postulates for associativity. (A,B)a,C)a DA 1(a) (A,(B,C)a)a D (A,(B,C)a)a DA 2(a) (A,B)a,C)a D These postulates
22、encode the associativity of the mode of combination a. Simi- larly, the Lambek-van Benthem calculus van Benthem 1983, often called LP, is derived with a single binary mode of combination p, along with the postulates of associativity and permutation. (A,B)p,C)p DA 1(p) (A,(B,C)p)p D (A,(B,C)p)p DA 2(
23、p) (A,B)p,C)p D (B,A)p CP(p) (A,B)p C Morrill defi ned a wrapping mode w, and allowed it to interact with the non- associative mode n and the associative mode a. The logic is determined by the binary modes BinMod = a,n,w and no unary modes. The non-associative mode is not subject to structural rules
24、 (on its own) the associative mode a is subject to the associative rules above, and the wrapping mode interacts with the other two modes according to the following schemes. (1,2)n,3)w A (1,3)a,2)a A (1,3)a,2)a A (1,2)n,3)w A Next, consider the following examples of structural postulates for unary mo
25、des of combination given by Moortgat 1994. ()u A 4(u) ()u)u A ()u AT(u) A 4 In addition to postulates governing the behavior of a single mode of combi- nation, Moortgat allows for mixed postulates, which allow the binary associative mode a to interact or communicate with a unary mode u (in order to
26、encode the Hepple/Morrill approach to bounding domains). (1)u,2)a AK 1(u,a) (1,2)a)u A (1,(2)u)a AK 2(u,a) (1,2)a)u A (1)u,(2)u)a AK(u,a) (1,2)a)u A It is also possible to use a unary operator p in conjunction with a binary operator a in order to condition permutation Morrill 1994. ()p,)a AP(a,p) (,
27、()p)a A In linear logic, unary modes have been used to import more liberal control over resources into a more restrictive logic.For instance, there is a mode, typically written !, which allows both weakening and contraction, as below. It is typically subject to the K structural rule and mixed with t
28、he commutative and associative binary mode p. (,()!)p A ()! A A ()!,)p A The fi rst rule allows the resource to be duplicated, and the second allows it to be eliminated. Often, the second rule above is used in the context of a nullary mode corresponding to the empty set of assumptions, but we will n
29、ot need recourse to nullary modes in our development. Assuming an alphabet AtExp of atomic expressions, a lexicon is a fi nite set Lex whose elements are of the form e A, where A Cat and e Exp. In general, the set Exp of expressions is the least such that: AtExp Exp (e)u Exp if e Exp (e1,e2)b Exp if
30、 e1,e2 Exp Assuming a non-associative binary mode of combination, expressions behave rather like bracketed strings, and with associative combination, behave like strings. We can then extend our sequents to include arbitrary expressions as follows. A17 e1,.,An7 en C iff C and ei Ai Lex for 1 i n 5 He
31、re we take A17 e1,.,An7 en to be the result of replacing all occur- rences of Aiwith ei. 3Turing Completeness For the purposes of this paper, we note a few relevant points about the form of these rules. First, they may either add or delete structure, as evidenced by the schemes 4 and T above. Second
32、, they may work in only one direction, as evi- denced by the 4, K, and T schemes. No one has suggested any metatheoretical constraints on structural postulates other than that they are not conditioned by particular categories (though they can obviously be conditioned on the modes themselves). If arb
33、itrary structural schemes are allowed, we have the following immediate result. Theorem 1 (Turing Completeness) A set S AtExpof expressions is enumerable by a Turing machine if and only if there is a categorial grammar, containing a category A, such that e S if and only if e A is provable. Proof: ()
34、This is obvious because a Turing machine can eff ectively enumerate all possible proofs by breadth-fi rst search in the usual way. () Suppose S can be enumerated by a Turing machine.Then there is a general rewriting (Type 0) grammar G with a distinguished non-terminal C0 (usually called the start sy
35、mbol) such that e S if and only if C e (where is the usual transitive refl exive closure of the one-step substring rewriting relation). Suppose the fi nite set of non-terminals of G is V1,.,Vn. Then we defi ne a categorial grammar as follows. We take the set of unary modes to be u1,.,un(one for each
36、 non-terminal), and combine this with a single binary mode a. We take exactly one category symbol, C. We assume the structural postulates of associativity for a, and will thus omit the binary bracketings; that is, we use the notation A1Anfor (A1,A2)a,An)a. Now for every production Vi1Vik Vj1Vjmin th
37、e rewriting system, we assume the following structural postulate: ()j1()jm A ()i1()ik A Note that this scheme will entail, via the left rules for the various 3, the following: 3j1C 3jmC A 3i1C 3ikC A For every lexical relation Vi e in the rewriting system, we assume a lexical en- try e 3iC in the ca
38、tegorial grammar. Assuming C0= Vkis the distinguished (start) symbol of the rewriting system, we must show that e1ep 3kC if and only if Vk e1ep. But this result is trivial, because there is a one- to-one correspondence between allowable one-step rewritings in the rewriting 6 system and applications
39、of structural rules in the categorial grammar. Simply recall that we have a one-step rewriting 00in a rewriting grammar if 0is a rewriting rule in the grammar, and ,0and are sequences of terminals and non-terminals. Finally, we note that it will not be possible to apply a right rule of any sort, bec
40、ause no connectives will ever be generated on the right-hand side of a sequent. Further, no left rule can be used because there will never be a pattern that maches the left unary or binary modal rules. Usually a proof of Turing-completeness for a grammar formalism leads its proponents to think more
41、carefully about the metatheory in terms of exactly what is to count as a grammar. One rather unnatural aspect of the reduction in the proof is that it allows arbitrary amounts of structure to be inserted and retracted. In the original Lambek system, decidability was ensured by requiring subproofs to
42、 only involve subcategories of the categories in the sequent being proved.Unfortunately, such restrictions have been violated in more recent proposals. 4Sahlqvist Axioms and Decidability An interesting restriction on structural rules was suggested by Kurtonina 1996 in her thesis as a means of guaran
43、teeing completeness in a particular logical for- mulation of multi-modal categorial grammars. Kurtonina provides the following defi nition: A structural rule of the form is said to be a weak Sahlqvist axiom if and only if is a pure product formula, associated in any order, without repetitions of pro
44、position letters, and is also a pure product formula containing at least one product, all of whose atoms occur in . Kurtoninas motivation was to enable the proof of a powerful completeness theorem concerning the non-associative Lambek Calculus (NL) combined with a weak Sahlqvist axiom, the combinati
45、on of which leads to a complete proof theory for the models satisfying the corresponding frame conditions derived from the axiom. From the point of view of representational power, it is easy to see that the restriction to Sahlqvist axioms defeats our coding of Turing machines us- ing modal operators
46、.Because all applications of structural rules will never increase the size of the proof space beyond a fi nite limit, decidability for the non-associative calculus combined with any weak Sahlqvist axiom is guaran- teed. For now, we have to leave aside the important issue of whether the restriction t
47、o weak Sahlqvist axioms will be too restrictive or whether such axioms will be suffi ciently rich to allow us to adequately model natural language syntax and semantics. 7 5Conclusion We have shown that mutlimodal categorial grammars can simulate arbitrary generalized rewriting systems by modeling their productions using structural interaction postulates. Without some restriction, such as to the weak Sahlqvist axioms, the universal decision problem for the grammaticality of a string with respect to a grammar is undecidable. This places multimodal cat