Upper and lower bounds


Alexander Clark

A small methodological issue. Suppose you are interested in identifying some single ingredient behind the faculty of language, some property that distinguishes humans from non-humans. This has to be some property that humans have that non-humans don’t have. So the argument needs to have two parts: a claim that humans have this property and a claim that non-humans don’t have this property. So this can’t be an upper bound on the human ability, but needs to be a lower bound.

People often use terms which are technically upper bounds as informal lower bounds. So one might say that the language $$L_1 = \{a^n b^n \mid n > 0 \}$$ is a context-free language. This is true of course. The language $$L_2 = \{a^m b^n \mid m,n > 0 \}$$ is also a context-free language. This second one is of course a regular language as well, but since all regular languages are also context-free languages this is also a CFL. Sometimes people want to distinguish these two by saying that the first is a proper context-free language, i.e. one that is not a regular language. This is undesirable as it privileges the regular/context-free boundary. The first language is a linear language, which means it can be generated by a grammar with at most one nonterminal on the right hand side of the productions. This is a proper subclass that lies between the regular and context-free classes. So from this perspective L1 is not a proper CFL either. If you want to say something is not regular, then just say it. Of course, informally we have some Gricean implicature that if we say a language is context-free we mean not regular as well, or we would say it is regular. But formally we should avoid this. One problem is what it means when we say something is not a CFL. Normally this could mean that it is not generated by any context-free grammar, but it could mean, speaking imprecisely that it is only a regular language.

Back to the faculty of language. Suppose the claim is that the magic ingredient is recursion. There is some disagreement about what this means, to say the least, (Tomalin, 2007), but Chomsky has been fairly consistent that this just means recursively enumerable in the standard computer science sense. But this is clearly an upper bound and doesn’t work in this argument, since saying that non-humans aren’t recursive in this sense would amount to saying that they are more powerful than humans.

So that is an uncharitable reading. Let’s be reasonable about this and try to change the argument a bit so it makes more sense technically. Presumably the claim is that non-humans are restricted computationally to only use rules that are not recursive in some sense. The emphasis then shifts to providing an upper bound on what non-humans can do.

So for example a directly recursive production in a context-free grammar looks like: $$ A \to XAY $$

So one might want to claim that non-humans can use phrase structure grammars that do not have rules like this. Of course one can have the same effect with two productions, neither of which is directly recursive, but which combine to derive the right hand side from the left.

$$ A \to XB, B \to AY $$

So this doesn’t quite work. But for example one could consider only productions that look like $$ A \to aB $$ and $$ A \to a $$ where a is a terminal and A and B are nonterminals. This would of course mean that the grammar can only generate regular languages.

This is a better argument, at least formally. Chomsky is probably correct that there aren’t any non trivial upper bounds on the computations that humans can carry out, other than those given by computational complexity and the finite size of the brain. It’s not at all clear whether it’s different for non-human animals, and whether the difference corresponds to any of the various notions of recursion on the table.

References

Tomalin, Marcus. “Reconsidering recursion in syntactic theory.” Lingua 117.10 (2007): 1784-1800.

Alexander Clark
comments powered by Disqus