It is idiomatic to ask what the meaning of a sentence is. Not everyone thinks that there are such entities as meanings to be ‘systematically pair[ed with] expressions’ (Speaks, ‘Theories of Meaning’: § 2.2.1). But even if there are no meanings, there are facts in virtue of which claims about meaning (e.g. synonymy) can be grounded. So, for instance, we might give a semantics for a language according to which, ‘[f]or all formul[æ] , is [true] iff if it is not the case that is true’ (Lepore and Ludwig, Donald Davidson's Truth-Theoretic Semantics){30}.
We might then expect some sort of procedure by which linguistic expressions are cognitively transformed during the process by which we come to understand them. One question is how those expressions are cognitively transformed (presumably by some physical process).
Pagin (‘Compositionality, computability, and complexity’) argues that the way these transformations operate is compositional that is to say, the results on a complex expression are (to a first approximation) determined by the results on its constituents. Consider e.g. the clause for above.
The argument is, in effect, that the transformations would take too long if they were not compositional. ‘Too long’ here is given in terms of the asymptotic analysis of the transformations a linguistic expression can undergo.
We will now give the formal details of the argument in slightly modified form.
ibid.
Is this a good argument? I think there is reason to be sceptical of asymptotic arguments like this in general, for the reasons outlined in Some varieties of idealisation. There is, however, more specific reason to be sceptical.
Consider the problem of anaphoric dependency. Some linguistic elements presumably cannot share referents. For instance: in the sentence ‘the murderer, John, shot him unprovoked’, the referent of ‘him’ is not the same as the referent of ‘John’. The anaphora problem is to systematically establish which linguistic elements cannot share referents. According to Ristad (Game: §§ 4.1–2), it is NP-hard.
I think this suggests that it is wrong to rule out that linguistic competence requires the solution of NP-hard problems on problems of small size. Ristad’s proof can be taken to show that (on plausible assumptions) the introduction of fresh pronouns (e.g. ‘him’) in resolving anaphoric dependencies probably is of exponential complexity. But that doesn’t mean that we solve these on obivously large cases.
Todo: transpose the formal details of Ristad’s argument.
Similarly, we should be cautious about Pagin’s argument; at most, it suggests that failures of compositionality must be somewhat bounded in the number of applications of -ary syntactic operators for , but it does not generally justify compositionality. Might it not transpire, for instance, that we are simply not very good at considering e.g. tenth-order belief?