Comments on lecture 2; part deux

In the first post (here), I discussed Chomsky’s version of Merge and the logic behind it.  The main idea is that Merge, the conceptually simplest conception of recursion, has just the properties to explain why NL Gs generate structures with unbounded hierarchical structure, why NLs allow displacement, show reconstruction effects, and why rules of G are structure dependent. Not bad for any story. Really good (especially for DP concerns) if we get all of this from a very simple (nay, simplest) conception. In what follows I turn to a discussion of the last three properties Chomsky identified and see how he aims to account for them. I repeat them here for convenience.

(v)           its operations apply cyclically

(vi)          it can have lots of morphology

(vii)        in externalization only a single “copy” is pronounced

In contrast to the first four properties, the last three do not follow simply from the properties of the conceptually “simplest” combination operation. Rather Chomsky argues that they reflect principles of computational efficiency. Let’s see how.

With respect to (vii), Chomsky assumes that externalization (i.e. “vocalizing” the structures) is computationally costly. In other words, actually saying the structures out loud is hard. How costly? Well, it must be more costly than copy deletion at Transfer is. Here’s why. Given the copy theory as a consequence of Merge, FL must contain a procedure to choose which copy/occurrence is pronounced (note: this is not a conceptual observation but an inference based on the fact that typically only one copy is pronounced). This decision/choice, I assume, requires some computation. I further assume that choosing which copies/occurrences to externalize requires some computation that would not be required were all copies/occurrences pronounced. Chomsky’s assumption is that the cost of choosing is less than the cost of externalizing.  Thus, FL’s choice lowers overall computational cost.

Furthermore, we must also assume that the cost of pronunciation also exceeds the computational cost of being misunderstood for otherwise it would make sense for FL to facilitate parsing by pronouncing all the copies, or at least those that would facilitate a hearer’s parsing of our sentences. None of these assumptions are self-evidently true or false. Plus, the supposition that copy deletion is more computationally efficient than pronouncing them would be does not follow simply from considerations of conceptual simplicity, at least as far as I can tell. It involves substantive assumptions about actual computational costs, for which, so far as I can tell, we have little independent evidence.

One more point: If copy deletion exists in Transfer to the CI interface (as Chomsky argued in his original 1993 paper and that underlies standard accounts of reconstruction effects and that so far as I know is still part of current theory) then in the normal case only a single copy/occurrence makes it to either interface, though which copy is interpreted at CI can be different form the copy spoken at AP (and this is typically how displacement is theoretically described). But if this is correct, then it suggests that Chomsky’s argument here might need some rethinking. Why? If deletion is part of Transfer to CI then copy deletion cannot be simply a fact about the computational cost of externalization, as it applies to the mapping of linguistic objects to the internal thought system as well. It seems that copies per se are the problem, not just copies that must be pronounced.

Before moving on to (v) and (vi) it is worth pausing to note that Chomsky’s discussion here reverberates with pretty standard conceptions of computational efficiency (viz. he is making claims about how hard it is to do something). This moves away from the purely conceptual matters that motivated the discussion of the first four features of FL. There is a very interesting hypothesis that might link the two: that the simplest computational operation will necessarily be embedded in a computationally efficient system. This is along the lines of how I interpreted the SMT in earlier posts (linked to in the first part of this post).  However, whether you think this is feasible, it appears, at least to me, that there are two different kinds of arguments being deployed to SMT ends, a purely conceptual one and a more conventional “resource” argument.

Ok, let’s return to (v) and (vi). Chomsky suggests that considerations of computational efficiency also account for these properties of. In particular, they follow from something like the strict cycle as embodied in phase theory.  So the question is what’s the relation between the strict cycle and efficient computation?

Chomsky supposes that the strict cycle, or something like it, is what we would expect from a computationally well-designed system. There are times that (to me) Chomsky sounds like he seems to be assuming that the conceptually simplest system will necessarily be computationally efficient.[1] I don’t see why. In particular, if I understand the lecture correctly, Chomsky is suggesting that the link between conceptual simplicity and computational efficiency should follow as a matter of natural law. Even if correct, it is clear that this line of reasoning goes considerably beyond considerations of conceptual simplicity. What I mean is that even if one grants that the simplest computational operation will be something like Merge, it does not follow that the simplest system that includes Merge will also incorporate the strict cycle.  Phases then, (Chomsky’s mechanism for realizing the strict cycle) are motivated not on grounds of conceptual simplicity alone but on grounds of efficiency (i.e. a well/optimally designed system will incorporate something like the strict cycle). So far as I can tell Chomsky does not explain the relation (if any) between conceptual simplicity and computationally efficiency, though to be fair, I may be over-interpreting his intent here.

This said how does the strict cycle bear on computational efficiency? It allows computational decisions to be made locally and incrementally. This is a generically nice feature for computational systems to have for it simplifies computations.[2] Chomsky notes that it also simplifies the process of distinguishing two selections of the same expression from the lexicon vs two occurrences of the same expression. How does it simplify it? By making the decision a bounded one. Distinguishing them, he claims, requires recalling whether a given occurrence/copy is a product of E- or I-Merge. If such decisions are made strict cyclically (at every phase) then phases reduce memory demand: because phases are bounded, you need not retain information in memory regarding the provenance of a valued occurrence beyond the phase where an expression’s features are valued.[3] So phases ease the memory burdens that computations impose. Let me note again without further comment, that if this is indeed a motivation for phases, then it presupposes some conception of performance for only in this kind of context do resource issues (viz. memory concerns) arise. God has no need for bounding computation.

Now I have a confession to make.  I could not come up with a concrete example where this logic is realized involving DP copies, given standard views.  It’s easy enough to come up with a relevant case if e.g. reflexivization is a product of movement.[4] If reflexives involve A-chains with two thematically marked “links” then we need to distinguish copies from originals (e.g. Everyone loves himself differs from everyone loves everyone in that the first involves one selection of everyone from the lexicon (and so one chain with two occurrences of everyone) while the second involves two selections of everyone from the lexicon and so two different chains). However, if you don’t assume this, I personally had a hard time finding an example of what’s worrying Chomsky, at least with copies. This might mean that Chomsky is finally coming to his senses and appreciating the beauty of movement theories of Control and Binding OR it might mean that I am a bear of little brain and just couldn’t come up with a relevant case. I know which option I would bet on, even given my little brain, and it’s not the first. So, anyone with a nice illustration is invited to put it in the comments section or send it to me and I will post it. Thanks.

It is not hard to come up with cases that do not involve DPs, but the problem then is not distinguishing copies from originals. Take the standard case of Subject-Predicate agreement for example. Here the unvalued features of T are valued by those of the inherently valued features of the subject DP.  Once valued, the features on T and D are indistinguishable qua features. However, there is assumed to be an important difference between the two, one relevant to the interpretation at the CI interface. Those on D are meaning relevant but those on T are uninterpretable. What, after all, could it mean to say that the past tense is first person and plural?[5] If one assumes that all features at the interfaces must be interpretable at those interfaces if they make it there, then the valued features on T must disappear at Transfer to CI. But if (by assumption) they are indistinguishable from the interpretable ones on D, the computational system must remember how the features got onto T (i.e. by valuation rather or inherently). The ones that get there by valuation in the grammar must be removed or the derivation will not converge. Thus, Gs need to know how features get onto the expressions they sit on and it would be very nice memory-wise if this was a bounded decision.

Before moving on, it’s worth noting that even this version of the argument is hardly straightforward. It assumes that phi-features on T are not-interpretable and that these cause derivations to crash (rather, then, for example, converge as gibberish) (also see note 5). It also requires that deletion not be optional, otherwise there would be derivations where all the good features remained on all of the right objects and all of the uninterpretable ones freely deleted. Nor does it allow Transfer (which, after all, straddles the syntax and CI) to peak at the meaning of T during Transfer, thereby determining which features are interpretable on which items and so which should be deleted and which retained. Note that such a peak-a-boo decision to delete during Transfer would be very local, relying just on the meaning of T and the meaning of phi-features. Were this possible, we could delay Transfer indefinitely. So, to make Chomsky’s argument we must assume that Transfer is completely “blind” to the interpretation of the syntactic objects at every point in the syntactic computation including the one that interfaces with CI. This amounts to a very strong version of the autonomy of syntax thesis; one in which no part of the syntax, even the rules that directly interface with the interpretive interfaces, can see any information that the interfaces contain.[6]

Let’s return to the main point. Must the simplest system imaginable be computationally efficient? It’s not clear. One might imagine that the conceptually “simplest” system would not worry about computational efficiency at all (damn memory considerations!). The simplest system might just do whatever it can and produce whatever structured products it can without complicating FL with considerations of resource demands like memory burdens. True, this might render some products of FL unusable or hard to use (and so we would probably perceive their use as perceive them as unacceptable) but then we just wouldn’t use them (sort of like what we say about self-embedded clauses).  So, for example, we would tend not to use sentences with multiple occurrences of the same expressions where this made life computationally difficult (e.g. you would not talk about two Norberts in the same sentence). Or without phases we might leave to context the determination of whether an expression is a copy or a lexical primitive or we might allow Transfer to see if features on an expression were kosher or not. At any rate, it seems to me that all of these options are as conceptually “simple” as adding phases to FL unless, or course, phases come for free as a matter of “natural law.”  I confess to being skeptical about this supposition. Phases come with a lot of conceptual baggage, which I personally find quite cumbersome (reminds me of Barriers actually, not one of the aesthetic high points in GG (ugh!)). That said, let’s accept that the “simplest” theory comes with phases. 

As Chomsky notes, phases themselves come have complex properties.  For example, phases bring with them a novel operation, feature lowering, which now must be added to the inventory of FL operations. However, feature lowering does not seem to be either a conceptually simple or cognitively/computationally generic kind of operation. Indeed, it seems (at least to me) quite linguistically parochial. This, of course, is not a good thing if one’s sights are set on answering Darwin’s problem.  If so, phases don’t fit snugly with the SMT. This does not mean there are none. It just means that they complicate matters conceptually and pull against Chomsky’s first conceptual argument wrt Merge.

Again, let’s put this all aside and assume that strict cyclicity is a desirable property to have and that phases are an optimal way of realizing this. Chomsky then asks how we identify phases? He argues that we can identify phases by their heads as phase heads are where unvalued features live. Thus a phase is the minimal domain of a phase head with unvalued features.[7] A possible virtue of this way of looking at things is that it might provide a way of explaining why languages contain so much morphology. They are the adventitious by-products for identifying the units/domain of the optimal computational system.  Chomsky notes that what he means by morphology is abstract (a la Vergnaud), so a little more has to be said, especially given that externalization is costly, but it’s an idea in an area where we don’t have many (see here).[8]

One remark: on this reconstruction of Chomsky’s arguments, unvalued features play a very big role. They identify phases, which implement strict cyclicity and are the source of overt morphology.  I confess to being wary here. Chomsky originally introduced unvalued features to replace uninterpretable ones. Now he assumes that features are both +/- valued and +/- interpretable. As unvalued features are always uninterpretatble, this seems like an unwanted redundancy in the feature system.  At any rate, as Chomsky notes, uninterpretable features really do look sort of strange in a perfect system. Why have them only to get rid of them?  Chomsky’s big idea is that they exist to make FL computationally efficient. Color me very unconvinced.

So this is the main lay of the land. I should mention that, as others have pointed out (especially Dennis O), part of Chomsky’s SMT argument here (i.e. the one linked to conceptual simplicity concerns) is different from the interpretation of the SMT that I advanced in other posts (here, here, here).  Thus, my version is definitely NOT the one that Chomsky elaborates when considering these. However, there is a clear second strand dealing with pretty standard efficiency concerns, and here my speculations and his might find some common ground. That said, Chomsky’s proposals rest heavily on certain assumptions about conceptual simplicity, and of a very strong kind. In particular, Chomsky’s argument rests on a very aggressive use of Occam’s razor.  Here’s what I mean. The argument he offers is not that we should adopt Merge because all other notions are too complex to be biologically plausible units of genetic novelty. Rather, he argues that in the absence of information to the contrary, Occamite considerations should rule: choose the simplest (not just a simple) starting point and see where you get. Given that we don’t know much about how operations that describe the phenotype (the computational properties of FL) relate to the underlying biological substrate that is the thing that actually evolved, it is not clear (at least to me) how to weight such strong Occamite considerations. They are not without power, but, to me at least, we don’t really know how to assess whether all things are indeed equal and how seriously to weight this very strong demand for simplicity

Let me end by fleshing this out a bit.  I confess to not being moved by Chomsky’s conceptual simplicity arguments. There are lots of simple starting points (even if some may be simpler than others). Ordered pairs are not that much more conceptually complex than sets. Symmetric operations are not obviously simpler than asymmetric ones, especially given that it appears that syntax abhors symmetry (see Moro and Chomsky). So, the general starting point that we need to start with the conceptually simplest conception of “combination” and that this means an operation that creates sets of expressions seems based on weak considerations. IMO, we should be looking for basic concepts that are simple enough to address DP (and there may be many) and evaluate them in terms of how well they succeed in unifying the various apparently disparate properties of FL. Chomsky does some of this here, and it’s great. But we should not stop here. Let me given an example.

One of the properties that modern minimalist theory has had trouble accounting for is the fact that the unit of syntactic movement/interpretation/deletion is the phrase. We may move heads, but we typically move/delete phrases. Why? Right now standard minimalist accounts have no explanation on hand. We occasionally hear about “pied piping” but more as an exercise in hand waving than in explanation. Now, this feature of FL is not exactly difficult to find in NL Gs. That constituency matters is one of the obvious facts about how displacement/deletion/binding operates. There is a simple story about this that labels and headedness can be used to deliver.[9] If this means that we need a slightly less conceptually simple starting point than sets, then so be it.

More generally: the problem that motivates the minimalist program is DP. To address DP we need to factor out most of the linguistic specific structure of FL and attribute it to more cognitively generic operations (or/and, if Chomsky is right, natural laws).  What’s simple in a DP context is not what is conceptually most basic, but what is simple given what our ancestors had available cognitively about 100k years ago. We need a simple addition to this, not something that is conceptually simple tout court.[10]  In this context it’s not clear to me that adding a set construction operation (which is what Merge amounts to) is the simplest evolutionary alternative. Imagine, for example, that our forbearers already had an itterative concatenation operation.[11]  Might not some addition to this be just as simple as adding Merge in its entirety? Or imagine that our ancestors could combine lexical atoms together into arbitrarily big unstructured sets, might not an addition that allowed that operation to yield structured sets be just as simple in the DP context as adding Merge? Indeed, it might be simpler depending in what was cognitively available in the mental life of our ancestors.  And once we are at it, how “simple” is an operation that forms arbitrary sets from atoms and other sets?  Sets may be simple objects with just the properties we need, but I am not sure that operations that construct them are particularly simple.[12]

Ok, let me end this much too long second post. And moreover, let me end on a very positive note. In the second lecture Chomsky does what we all should be doing when we are doing minimalist syntax. He is interested in finding simple computational systems that derive the basic properties of FL. He concentrates on some very interesting key features: unbounded hierarchy, displacement, reconstruction, etc. and makes concrete proposals (i.e. he offers a minimalist theory) that seem plausible. Whether he is right in detail is less important IMO than that his ambitions and methods are worth copying. He identifies non-trivial properties of FL that GG has discovered over the last 60 years and he tries to explain why they should exist.  This is exactly the right kind of thing MPers should be doing. Is he right? Well, let’s just say that I don’t entirely agree with him (yet!). Does lecture 2 provide a nice example of what MP research should look like. You bet. It identifies real deep properties of FL and sees how to derive them from more general principles and operations. If we are ever to solve Darwin’s problem, we will need simple systems that do just what Chomsky is proposing. 

---

[1] Note, we want the necessarily here. That it is both simple and efficient does not explain why it need be efficient if simple.

[2] It is also a necessary condition for incrementality in the use systems (e.g. parsing), as Bill Idsardi pointed out to me.  I know that the SMT does not care about use systems according to some (Dennis and William this is a shout-out to you), but this is a curious and interesting fact nonetheless.  Moreover, if I am right that the last three properties do not follow (at least not obviously) from conceptual considerations, it seems that Chomsky might be pursuing a dual route strategy for explaining the properties of FL.

[3] Note that this assumes that there is no syntactic difference between inherent features and features valued in the course of the derivation.

[4] And even this requires a special version of the theory, one like Idsardi and Lidz’s rather than Zwart’s.

[5] However, if v raised to T before Transfer then one might try and link these features to the thematic argument that v licenses. And then it might make lots of sense to say that phi-features are interpretable on T. They would say that the variable of the predicate bound by the subject must have such and such an interpretation. This information might be redundant, but it is not obviously uninterpretable.

[6] The ‘autonomy of syntax’ thesis refers to more than one claim. The simplest one is that syntactic primitives/operations are not reducible to phonetic or semantic ones. This is not  the version adverted to above. This is a more specific version of the thesis; one that requires a complete separation between syntactic and semantic information in the course of a derivation. Note, that the idea that one can add EPP/edge features only if it affects interpretation (the Reinhart-Fox view that Chomsky has at times endorsed) violates this strong version of the autonomy thesis.

[7] Note, we still need to define ‘domain’ here.

[8] Note, incidentally, that Chomsky assumes both that features are +/- valued and that they are +/- interpretable. At one time, the former was considered a substitute for the latter. Now, they are both theoretically required, it seems. As -valued features seem to always be –interpretatble, this seems like an unwanted redundancy. 

[9] I provide a story here based on labels and minimality.

[10] A question: we can define ordered pairs set theoretically. I assume the argument against labels is that ordered sets are conceptually more complex than unordered sets. So {a,b} is conceptually simpler than {a,{a,b}}.  If this is the argument, it is very very subtle. I find it hard to believe that whereas the former is simple enough to be biologically added, the latter is not. Or even that the relative simplicity of the two could possibly matter. Ditto for other operations like concatenation in place of Merge as the simplest operation.  Given how long this post is already, I will refrain from elaborating these points here.

[11] Birds (and mice and other animals) can string “syllables” together (put them together in a left/right order) to make songs. From what I can tell, there is no hard upper bound on how many syllables can be so combined.  These do not display hierarchy, but they may be recursive in the sense that the combination operation can iterate. Might it not be possible that what we find in FL builds on this iteration operation? That the recursion we find in FL is iteration plus something novel (I have suggested labeling is the novelty)? My point here is not that this is correct, but that the question of simplicity in a DP context need not just be a matter of conceptual simplicity.  

[12] How are sets formed? How computationally simple is the comprehension axiom in set theory, for example? It is actually logically quite involved (see here). I ask because Merge is a set forming operation, so the relevant question is how cognitively complex is it to form arbitrary sets. We have been assuming that this is conceptually simple and hence cognitively easy. However, it is worth considering just how easy. The Wikepedia entry suggests that it is not a particularly simple operation. Sets are funny things and what mental powers go into being able to construct them is not all that clear.

Minimalism and Computational Complexity

If you ever want to make a computer science (CS) savvy linguist wince start talking about minimalism and its efforts to reduce computational complexity.  After the wincing (usually followed by some twitching), a question plus a lament pops out. The lament centers on reminding the speaker (it’s happened to me at least thrice in various venues) that “[t]here is already a very well developed science of computation—it’s called computer science (nothing to do with computers though!)” and the question is “Could you explain why Minimalism rejects CS?” The quotes come from a perfectly reasonable comment by Andy Clark on this post where ‘complexity’ and ‘minimalism’ are found in close proximity. Both the lament and the question deserve a response. I’ll try to give one below.[1] However, before plowing ahead, let me re-emphasize that I find these responses both reasonable and all too comprehensible. It has taken me a long time to work up the kind of answer provided below. It’s not clear to me how much this fits with Chomsky’s own intended views, but I believe that this fits acceptably well with the intentions of the Minimalist Program and is a notion of complexity that is well worth exploring. I would be interested in feedback from those out there who have worried about these issues: How well does it fit with conceptions you have had? How well does it fit with the programmatic outlines of Minimalism? Do you find this take on the issue worthwhile?  All comments welcome given the conceptually flocculent and difficult nature of the proposed enterprise. So here goes. 

Oh yes, the ‘we’ you encounter below is not royal (though my mother assures me that I am ‘a prince’).  It alludes to the joint authorship (with Bill Idsardi) of the ideas expressed. One last caveat to you lectors: this is a VERY LONG post with a selected bibliography and lots of notes. Teach Alex to get me going. Here goes again:

There are many ways of measuring efficiency/complexity and before going on we would like to review some to clarify how we believe that minimalists (should) understand the concept.

There are at least two of relevance here. The first, the one that those with a computational background generally reach for, might be dubbed “Problem Complexity” (PC)[2]. Some problems are hard no matter what kind of computing device or algorithms one envisages, e.g. NP-hard problems like the traveling salesman problem.[3] The resources needed to solve these problems in the general case scale exponentially. So for example, though it is possible to compute the shortest route among 5 cities, there is no general efficient way to compute the shortest route for arbitrary N cities for as N grows the resources required to consider the options grows exponentially. It is widely believed that this kind of problem cannot have a computationally reasonable solution covering all cases (though the P ≠ NP conjecture still evades proof), even though there are algorithms that can give you pretty good solutions over reasonably large N or can give optimal solutions for special sub-cases. These are the kinds of problems that are of central interest to complexity theorists within CS for they are problems that lend themselves to general results. It is doubtful, however, that these are the kinds of problems that will be of central concern to those interested in biological computation. The main reason for this is that in order to say something general (something that lends itself to the standard methods of proof), these problems abstract away from specific algorithms and hardware. They are hard regardless of the “machines” they run on or the algorithms they exploit as the time (or space) required for their solution will always outpace the resources available in the general case, i.e. where N goes to infinity in the problem above. However, as has been previously noted,[4] in the case of cognitive computation we are not exclusively interested in this notion of computation precisely because it abstracts away from the properties of particular data structures, the particular algorithms that use them and the particular hardware they run on. In fact, if one’s main interest is in the data structures, algorithms and machine architecture of the biological system one is studying (i.e. is interested in the structure of FL both narrow and wide) then such wholesale abstraction distances us from the problem of interest, i.e. the structure of FL. [5] Thus, it seems to us that when minimalists point to issues of computational complexity it is not complexity in this sense that they should have in mind (though it is what’s available off-the-shelf).

Another notion of complexity is “Effective Complexity” (EC), sometimes discussed as “computational efficiency” and, we believe, what Chomsky might mean by “operational complexity.” There are no general theorems about EC because they are closely tied to the details of the specific computational settings where they arise. In fact, it is known that there cannot be a general theory.[6] These problems are situated; they care about the algorithms used, the architectural resources available, and the problems being addressed.[7] In these contexts there are interesting issues of “fit” between the shape of the data structures, the algorithms using them and the machines running them. In the CS world these concerns arise in the context of writing code. Here practitioners distinguish between good programs and bad ones with respect to how well they run on actual (or conventionalized hypothetical) systems. Particular data structures can be (and are) judged more effective or efficient than bad ones in specific contexts. These contexts can be narrower or wider. So it is possible that some kinds of programs will run better on machines with some kinds of memory or that some data structures are more suitable given the structure of some kinds of algorithms or some kinds of hardware. Thus, though there may not be anything of general interest that one can show (general in the sense of abstracting away from the details of architecture, algorithm and data structure), it does not mean that there are not decent mid-level generalizations that can be reasonably applied to evaluate particular proposals. A couple of examples might make this clearer.

Consider first the problem of representing a sequence of items, usually termed a list. This is discussed in detail in Chapter 2 of Aho, Hopcroft and Ullman (1983) and in virtually every other book on algorithms and data structures. Similar to Marr’s discussion of a computational definition of a cash register through its basic operations, we need to define some basic operations on lists, such as INSERT, DELETE, NEXT and FIRST. We can then discuss how complicated various implementations of these operations would be using different ways to represent lists. One way to represent a list would be like a column of values in an Excel spreadsheet. The first cell, A1, will contain the first element, the second cell, A2, the second and so on. Consider what we would need to do to insert an element into the tenth position of the list. We would need first to open up the tenth position to be able to accept the new value. This entails moving all of the subsequent values down one position. So, in general, the time complexity of this operation will depend on the size of the list being inserted into, and will take different amounts of times depending on how much list follows the insertion position. We can compare this with the list represented with pointers (also called cons-cells, or linked lists). Each element is stored in a little structure that has two parts, the value being stored and a pointer to the next structure in the list. Here is their diagram:

Now, to insert into the tenth position we don’t need to move any of the subsequent items. They can stay where they are. What we do need to do is to make the ninth cell point to the new cell, and for the new cell to point to old tenth cell. That is we need to add two new pointers and delete one old one. This has a constant cost regardless of where in the list we do the insertion.

Marr offers another familiar example, that of different base representations for numbers. We’ll take Tom Lehrer’s example from “New Math” (search YouTube) and compare base 10 with base 8 (“just like base 10 really, if you’re missing two fingers”). Let’s consider the number 96, which is “96” in base 10 (9 x 10 + 6 x 1) and “140” in base 8 (1 x 64 + 4 x 8 + 0 x 1). In both base 10 and base 8 it’s easy to tell if a number is even (i.e. divisible by 2) just look at the final digit, and if it is 0, 2, 4, 6, or 8 (although “8” doesn’t exist in base 8 of course) then it’s even. This is because all powers of 8 and 10 are themselves even and so quantities in the higher place-positions are idempotent with respect to evenness. But if we want to know if a number is divisible by 4 there is a difference. In base 8 this is again easy, just look at the final digit and if it is 0 or 4, then it is divisible by 4 because powers of 8 are also idempotent for 4-multiple-ness. But powers of 10 are not all idempotent for 4-multiple-ness. 10 is not divisible by 4, but 100, 1000, etc. all are. So to determine whether a base 10 number is divisible by 4 we need to look at the last two digits. If the tens-place digit is even and if the ones-place digit is 0, 4 or 8 then it is divisible by 4 (i.e. 4, 8, 20, 24, 28, 40, 44, 48, etc.); if the tens-place digit is odd and if the ones-place digit is 2 or 6 then it is also divisible by 4 (12, 16, 32, 36, etc.). This procedure is clearly more complicated for base 10 than for base 8 (though not that much more, we have to look at two digits instead of one, we don’t have to look at the entire digit string; base 7 is left as an exercise for the reader). Tricks based on such properties used to be taught in grade school under names like “casting out nines” (search WikiPedia); this will also determine whether a base 10 number is divisible by 3. This requires that we look at every digit, adding them up mod 9. So 327 (base 10) is divisible by 3 because 7 + 2 = 9 = 0 mod 9 and 0 + 3 = 3, which is one of 0, 3, 6. Marr’s conclusion is the same as ours: the details of the representational format matter, and some representations are better suited to some operations (linked lists are good for insertions, base 8 is good if you want to find multiples of 4).

Another nice example discussed by Gallistel and King (101-103) is the use of Cartesian versus polar coordinates for the encoding of locations. If dead reckoning found in animals like ants and bees involves path integration with respect to a privileged fixed location (e.g. the hive, colony), then polar coordinates are a very efficient way of coding locations.

These examples all illustrate the same basic point: some details of representation can really matter and though principled generalizations are hard to come by, in specific settings it is pretty clear that that some ways of proceeding are more efficient than others. The relevant issues for minimalists is whether there are plausible conclusions concerning the efficiency of linguistic data structures (one might dub this questions of “optimal coding”) that one can tease out given what we know about the properties of the biological systems that will use these. Chomsky (2005:9-10) has put the issue of computational complexity in these terms, emphasizing the fit between grammatical objects and the interfaces that use them for articulation (AP) and thinking (CI).

To what extent does language approximate an optimal solution to conditions that it must satisfy to be usable at all, given extralinguistic structural architecture?

We would like to expand the range of considerations beyond just interface fit. Our gloss on Chomsky’s framing of the issue is as follows: how do the data structures that constitute linguistic structure reflect good design in the sense of fitting well with the architectural properties of the systems that use them? Or, are there some principles of optimal coding that grammars embody given the computational environments where they are used?[8] Or, how do various complexity concerns look when viewed through the lens of effective complexity? Let’s take a running start and see.

The goal of Generative Grammar is to discover the computational procedure that generates an unbounded number of (p,l) pairs (pi/lambda).  We can think of this procedure as generating data structures that feed into the AP (sound) and CI (meaning) interface respectively. Let’s consider under what conditions this sort of system would be well designed: what makes a data structure better or worse, what makes a code optimal?  Our view (and I believe that Chomsky has this in mind, though exegesis will not be my main aim here) is that answering this question requires thinking about how these data structures will be (in the widest sense of the word) used.  We know several things about these (p,l) pairs. First, they interact with representations in the AP and CI systems.  In other words, (p,l) pairs contribute to how linguistic objects are pronounced and how they are used to think.  So, a well-designed generative procedure will produce data structures that interface with these (at least) two mental organs efficiently.  Though we don’t know exactly what this entails, one reasonable metric of evaluations would be to prefer that generative procedure that delivers linguistic representations/data structures that minimize the computational load of the interfaces that use them.

Chomsky gestures at an efficiency argument when he suggests that copies are minimized (“deleted”) so as to make their expression by the AP system easier, i.e. if p contains exactly one copy of a moved expression the AP system has to work less hard to “interpret” it.  In this sense, a copy reduced p is a superior data structure than one that retains all copies.  I don’t want to consider whether Chomsky is right about this particular case, but it provides a plausible computational “sketch” for understanding why movement chains generally have trace-like AP properties.

A similar kind of argument can be made for the l half of the (p,l) pair, though what CI representations look like is quite a bit more obscure than are the properties of the AP interface.  However, say that it looks something like an event structure à la Davidson and is regulated by something like UTAH then it would be reasonable to argue that being able to identify internal and external arguments in a l-representation for mapping to agents and patients in an event representation would be a very nice design feature for l-ish objects to have. Why, because it would smooth the mapping between the linguistic data structures and the CI interfaces that uses it. Understand ‘smooth’ to mean well designed in that it requires fewer computational steps to manage the “translation” from one kind of representation to the other, transparent mappings being computationally preferred.[9] Again, this is not yet an explanation, but it points towards the kinds of things we would expect from well-designed data structures and these relate to issues of computational complexity, in the sense of effective complexity, noted above.

There is a second aspect to use.  Linguistic data structures are used by creatures with specific kinds of memory and attention resources. In particular, mammalian memory (and attention) is finite and content addressable.  Here’s a computational question: might linguistic data structures reflect these resource burdens? For example, we know that long distance dependencies impose memory burdens in parsing.  We also know that data structures that are too similar are readily confused thus making use of such structures more difficult. Ok, here’s a conjecture: linguistic data structures reflect these very general features of human minds/brains.  This suggestion clearly riffs on minimalist themes. It proposes that linguistic data structures are optimally designed to mitigate the computational problems that these general architectural features of mammalian memory/attention necessarily lead to.   This leads to a research question: What properties might an “optimally” usable data structure have given that it is to be used to animals with memory/attention systems like ours?  To repeat, we are not dealing here with filigree features. That memory storage is not costless and that mammalian memory is content addressable are very general well-established features of human minds.  Why shouldn’t data structures that must “interact” with such systems reflect their design specifications? Why isn’t considering these abstract questions reasonably thought of as bearing on operational computational complexity? If you missed it, the last question is rhetorical.

Consider some examples: a well designed system might prefer shorter dependencies to longer ones and it may form dependencies where the “closest” featurally matched expression blocks access to more remote similarly feature endowed expressions. If this sounds a little like Relativized Minimality, good! Such memory/attention systems might also prefer cyclically applied operations so that computations take place in small manageable domains (I hope this sounds like subjacency/phases).  Chomsky adverts to these kinds of concerns when he points to “minimal search” as a computational virtue.  Why is that good? Because it mitigates resource constraints.  Note, that we are not really worried here about algorithmic details. The discussion is quite abstract, the boundary conditions being that humans have pretty small (finite) resources that they deploy when they use linguistic data structures. Would it be surprising if some data structures mitigated the effects of such resource constraints better than others?  I don’t see why.  After all, why should we only look at the computational consequences of linking to interfaces and not the consequences of finite content addressable memory?  If doing so means smudging the boundaries between competence and performance or data structures and algorithms, so be it.[10]  Sometimes attenuating a distinction is worthwhile.

I should note that these kinds of considerations are hardly novel with Minimalism.  For example, Chomsky 1977 presents computational arguments in favor of the Subjacency Principle, the Specified Subject Condition and the Tensed S Condition. Berwick and Weinberg (1984) show that data structures that incorporate locality restrictions on dependencies like subjacency can be nicely embedded in left corner parsers that allow for efficient parsing.  They also suggest that grammar size really matters when “realistic” sentence parsing is considered (say sentences of 20-30 words) and so compact grammatical representations (e.g. those that embody movement rather than sets of PS rules, or those that collapse operations reducing the number of dependencies) have computational consequences when viewed from the perspective of a system that uses these generative procedures.[11]  There is an intimate connection (as Marr (1982) and Gallistel and King (2009) show and which was noted above) between the shape of data structures (and hence the procedures that generate them) and the how they are used.

This is how I have approached the computational efficiency question.  It is very plausible to me that some features of linguistics data structures respond both to interface considerations and resource features of human use.  Let me end with a sample example or two.

Consider the Extension Condition (EC). EC can be restated as a kind of conservation law: phrases once created are not destroyed.  Moreover, it can be restated as a kind of symmetry principle: The analysis of a linguistic object from left to right and up to down yields the same constituents as synthesis of that structure from right to left and the bottom up. In other words, the phrases you get should be the same if you are putting a sentence together using the generative procedure or pulling it apart using that procedure.[12] Thus the “direction” of grammar use makes no difference. This property would be quite useful, for example, for any data structure that is used both in parsing and production. EC, thus, is a computationally nice property for a linguistic generative procedure to have.[13]

So too the Inclusiveness Condition (IC). IC can be understood as a conservation principle: the labels in the tree at the end of a derivation are the same as the labels in the initial numeration.[14] This has the effect that the interpretation of a linguistic object is purely a function of the lexical items involved and the relations they are put into.  Grammars do not add “idiosyncratic” structure to that already contained in lexical items. It is reasonable (at least to me) to treat lexical idiosyncracy as computational costly. IC bars it. 

So, it seems to me that there is a reasonable way of thinking about complexity within FL/UG (complexity of data structures) if one looks towards (i) how systems that interface with its products will use them and (ii) the kinds of memory/attention resources that human minds use in carrying out computations in real time. Following Marr and Gallistel and King I have noted that the shape of data structures can (and does in practice) reflect computational concerns, indeed exactly those kinds that minimalists can usefully explore.

Bibliography

Aho, A.V., J. D. Ullman and J. E. Hopcroft. 1983. Data structures and algorithms. New

York: Addison-Wesley

Baltin, M. 2003. The intereaction of ellipsis and Binding: implications for the sequencing

Of principle A. Natural Language and Linguistic Theory 21:215-246.

Baltin, M. 2006. The non-unity of VP preposing. Language 734-736.

Berwick, R.C. 1980. Computational analogues of constraints on grammars: A model of

syntactic acquisition. In 18^th Annual Meeting of the Association of Computational

Linguistics.

Berwick, R. C. and A. Weinberg. 1982. Parsing efficiency, computational complexity,

and the evaluation of grammatical theories. Linguistic Inquiry 13.2. 165-191.

Berwick, R. C. and A. Weinberg. 1984. The grammatical basis of linguistic performance.

            Cambridge: MA. MIT Press.

Chaitin, G. 1969. On the Simplicity and Speed of Programs for Computing Infinite Sets

of Natural Numbers. Journal of the Association for Computing Machinery 16: 407.

Chomsky, N. 1977. On wh-movement. In P.W. Culicover, T. Wasow and A. Akmajian

(eds.), Formal Syntax. Academic Press, 71-132.

Drummond, A. 2010. A note on the verb phrase constituency paradox. MS, UMD.

Gallistel, C.  R. and A.P. King. 2009. Memory and the computational brain. Oxford:

            Wiley-Blackwell.

Hornstein, N. A theory of syntax. 2009. Cambridge: CUP press.

Hornstein, N. Forthcoming. Three grades of grammatical involvement:

            syntax from a minimalist perspective. Mind and Language.

Hornstein, N. and W. Idsardi. Forthcoming. A program for the minimalist program.

Kolmogoro, A. N. 1965. Three Approaches to the Quantitative Definition of Information.

Problems in Information Transmission 1 (1): 1–7.

Lechner, W. 2003. Phrase Structure Paradoxes, Movement and Ellipsis.

In Schwabe, Kerstin & Winkler (eds.) The Interfaces: Deriving and

Interpreting Omitted Structures, Amsterdam: John Benjamins, 187-203.

Li, Ming and Vitányi, Paul, An Introduction to Kolmogorov Complexity and Its

Applications, Springer, 1997.

Marr, D. 1982. Vision. San Francisco: W. H. Freeman.

Solomonoff, R. Solomonoff, R. 1964. A Formal Theory of Inductive Inference Part I and

Part II. Information and Control 7: 1–22, 224-254.

---

[1] What follows is based on joint work with Bill Idsardi. We have a paper in a forthcoming volume that addresses these issues in more detail in the context of outlining a slightly

different program for Minimalism.  I will link to the paper when it is finished.

[2] C.f. Barton, Berwick and Ristad 1987.

[3] These are the kinds of problems that I believe Alex was alluding to (see above) when he noted parenthetically that this branch of CS has nothing to do with computers. For these kinds of concerns formalization is very important as the formalization is in service of proofs.  It is less clear that formalization is particularly important otherwise. There are some tidy minded types that believe that formalization is a virtue in itself. I am not one of those.

[4] C.f. Berwick and Weinberg 1982 for an excellent and relevant discussion.

[5] We would like to take the categorical tone out of this pronouncement. Methods of problem complexity might be relevant and enlightening. If one can establish that some kind of problem is NP-hard then it immediately implies that there will be no general optimal solution available. For some examples of this reasoning in the linguistic domain c.f. Barton, Berwick and Ristad (1987). For further discussion c.f. Berwick and Weinberg 1982, 1984.

[6] See works by Solomonoff, Kolmogorov, and Chaitin which comprise the basic materials in Algorithmic Information Theory. The basic result is that the Kolmogorov complexity is not a computable function. A useful introduction is provided by Li and Vitanyi 1997.

[7] See Gallistel and King for an elaborate discussion of this perspective.

[8] There are at least seven different notions of complexity alive within minimalist theorizing. We noted, PC and EC above. In addition the following can be found in the literature:

1.     Conceptual complexity, e.g. A notion of merge where the elements range over a larger domain is conceptually simpler than one that ranges over a smaller domain.

2.     Methodological Complexity: this is essentially Ockham’s Razor reasoning e.g. a theory with only levels that feed the interfaces (PF,LF) is conceptually preferable to one with four levels that include these two and DS and SS as well.

3.     Representational Complexity: e.g. Full Interpretation, all structure that FL feeds the CI interface is interpretable.

4.     Minimal Description Length: more compact representations are preferred to less compact ones. C.f. Berwick and Weinberg 1982 for how the size of a grammar is potentially relevant to evaluating parsing efficiency.

5.     Darwinian Complexity: FL is built up from the fewest language specific operations and constraints. The more the operations and principles FL that embodies are domain specific the more evolutionarily complex it is.

Each of these notions are interesting and relevant and worth keeping distinct.

[9] See Berwick and Weinberg (1982) for a discussion of transparency and for a discussion of the general setting for minimalist speculations such as these.  A useful companion piece is Berwick (1980).

[10] Incidentally, a careful reading of Marr (and more recently Gallistel and King) reveals that optimal design always considers the relation between what data structures look like and the systems that use them.  So, I don’t believe that these kinds of speculations are at odds with what Marr (and others) understand by optimal coding.

[11] Ed Stabler made a similar point at the Maryland Mayfest in 2012.

[12] Something like this is suggested in Hornstein 2009.  This is a clearer version: the idea being that how you use a grammar to build a sentence does not matter for the same constituents will appear.

[13] Note, incidentally, operations like Tucking In or Colin Phillips’ left to right generator discussed in Abel’s piece fail to have these properties. When stripping a phrase down from root to terminals a Tucking In derivation (e.g. in  [a[b […g…b…]]], if b tucks in under a, then [a[…g…b…]] was a constituent if generated bottom up but not when pulled apart top down. Similarly the whole point of Phillips top down derivational theory is to allow “temporary” constituents that could not be derived going bottom up, e.g. in ‘the dog from Brazil saw me’ the left to right generation has ‘the dog’ as a temporary constituent.  See Baltin (2003, 2006), Drummond 2010 and Lechner 2003 for reanalysis of the data in Phillips that motivated his top down approach.

[14] This too looks like a reflection of a symmetry principle: regardless of the operations and the lexical items used labels remain constant. Technically, given a numeration, the set of MaxPs at the start of a derivation is identical to the set at the end (understanding MaxP to be an expression not immediately dominated by a label distinct from itself).