In certain circumstances, we idealise the acceleration of a body on earth as if it were dropped in a vacuüm.

We could test the hypothesis by comparing the air pressure in a vacuüm and on earth. But this is ‘a foolish question by itself’. If we are dropping a ball from a building, its acceleration probably will closely approximate that in a vacuüm; but not a feather. So the putative accuracy of the antecedent idealisation is not, per se, a good guide to its legitimacy or usefulness. We should also consider the predictive inaccuracy it introduces.

Friemdan says that predictive accuracy is the ‘only relevant standard of comparison’. We need not go that far to appreciate the point that it is a relevant standard of comparison, and that the accuracy of the idealisation per se is not always relevant.

A function is feasibly computable if and only if some machine with polynomial runtime computes it (Cobham, Difficulty, Edmonds, Paths).

By conjecture, I mean a claim that is thought to straightforwardly be true, but for which we have no proof. For instance, Fermat’s last theorem was long a conjecture. By heuristic, I mean a claim counterexamples to which are accepted but which is thought generally to be at least approximately true. For instance, a useful heuristic in most engineering problems is to assume that relativistic effects are negligible; this is not true e.g. for GPS but is (at least approximately) true e.g. for most architectural purposes.

Certain processes are constitutive of human language: production, comprehension and acquisition. These are cognitive processes that map from inputs to outputs—e.g. from acoustic or visual signals to representation of linguistic information; they are ipso facto comptuations.

Ristad (Game: 1) seems to offer something like this argument.

So do Clark and Lappin (Nativism: § 4.1) in the context of language acquisition.

[T]he child is, among other things, an information processing system, and is subject to the laws that govern computational systems. By studying the theoretical bounds on learning systems, we can make important inferences about the limiting conditions of the empirical question. To take a simple analogy, the problem of determining how birds fly is an empirical matter, but it is also clear that the principles of aerodynamics are highly relevant to this study. The bird is subject to the laws of physics, and no plausible account will violate those laws. We can reject out of hand any explanation that does not conform to the principles of aerodynamics.

The invitation, then, is to reject out of hand any account of language or linguistic phenomena that does not conform, putatively, to the laws of computation, whence asymptotic analysis.

The physicalist argument proceeds in four steps, the latter three from Rooij et al. (Cognition: 14). First, we should study in terms of cognitive processes (e.g. acquisition and production). Second, postulation of some cognitive capacity entails commitment to some explanation as to how that capacity is realised. Third, physically feasible explanations of cognition must be ‘computable and tractable’. Fourth, by the invariance and Cobham–Edmonds thesis, such explanations must (to a first approximation) be in polynomial time.

Arora and Barak (Complexity: § 1.1).

Let $f$ be a function that takes a string of bits…and outputs either 0 or 1. An algorrthm for computing $f$ is a set of mechanical rules, such that by following them we can compute $f(x)$ given any input $x\in [0,1{]}^{\ast }$. The set of rules being followed is fixed (i.e. the same rule must work for all possible input) though each rule in this set may be applied arbitrarily many times. Each rule involves one or more of the following ‘elementary’ operations:

1. Read a bit of the input.
2. Read a bit…from the scratch pad or working space we allow the algorithm to use.

Based on the values read,

1. Write a bit/symbol to the scratch pad.
2. Either stop and output 0 or 1, or choose a new rule from the set that will be applied next.

Finally, the running time is the number of these basic operations performed.

1. why limit ourselves just to symbols 0 and 1?
2. why are the operations so limited? and
3. why not read multiple bits at the same time?

We say that the runtime of an algorithm is polynomial if its runtime is $f(n)\in O(n^k)$ for some fixed $k$.

Consider a list of two numbers, and a task: to sort the list in ascending order.

We will assume that only one operation is permitted.

How many comparison-cum-swaps do we need, on a list of two numbers, to sort it in ascending order? Clearly: one. For instance: if the list is $⟨1,2⟩$, the comparison-cum-swap immediately shows that they are in ascending order, so we are done. Alternatively, if the list is $⟨5,2⟩$, the comparison-cum-swap immediately shows they are in the wrong order, they are swapped, and then we are done.

Suppose the list contains three elements: for instance, $⟨1,2,3⟩$. How many comparison-cum-swaps do we need? One isn’t enough; we’d only be able to consider two of the numbers, and so the third number would have no effect on the final putatively sorted list we produce. What about two?

Two might be enough to verify that a list is sorted, if we’re lucky. Given $⟨1,2,3⟩$, we need only observe that $1<2$ and $2<3$.

However, two is not enough, in general, to sort a list (rather than simply to check whether it is actually sorted). Consider: every comparison-cum-swap leads to at most two possible orderings of some list $⟨a,b,c⟩$. So if there are two comparison-cum-swaps, there are at most $2\times 2=4$ orderings the procedure yields. But there are in fact six possible correct orderings of the list:

1. $⟨a,b,c⟩$,
2. $⟨a,c,b⟩$,
3. $⟨b,a,c⟩$,
4. $⟨b,c,a⟩$,
5. $⟨c,a,b⟩$, and
6. $⟨c,b,a⟩$.

We can pose the question for a problem of arbitrary size.

Given $n$ cities and the distances between them, what is the shortest path by which the salesman may visit each of them at least once?

Given a formula over $n$ literals in conjunctive normal form each of whose clauses has at most three literals, is there a satisfying assignment?

Given a monotonically non-decreasing function $g:\mathbb{N}\to \mathbb{N}$, we write $$\mathrm{\Theta }(g(n))=\{f(n):\text{there exist positive constants }{c}_1\text{, }{c}_2,\text{ and }{n}_0\text{ such that, for all }n⩾n_0\text{, }0⩽c_{1}g(n)⩽f(n)⩽c_{2}g(n)\}.$$

Given a monotonically increasing function $g:\mathbb{N}\to \mathbb{N}$, we write $$O(g(n))=\{f(n):\text{there exist positive constants }c\text{ and }{n}_0\text{ such that, for all }n⩾n_0\text{, }0⩽f(n)⩽cg(n)\}.$$

The task of sorting a list of $n$ numbers takes $\mathrm{\Theta }(nlogn)$ comparison-cum-swaps.

This thesis is about the application of asymptotic analysis from theoretical computer science to language.

Arguments from asymptotic analysis have been offered for varied conclusions, including Chomskyan universal grammar, compositionality, and the collapse of the competence/performance distinction.

• Asymptotic analysis of algorithms: I introduce asymptotic analysis.
• A model of computation: I introduce Turing machines as a model of computation with which to undertake asymptotic analysis.
• Computation, cognition and language: I explain how computational asymptotic analysis bears on the study of language, though perhaps as an idealisation.
• Some varieties of idealisation: I discuss some varieties of idealisation.
• An asymptotic argument for compositionality: I critically examine an asymptotic argument that meanings must be compositional.

We begin with a preliminary example.

Similarly, other problems of arbitrary size can be posed.

A generalisation of the argument above in fact gives the answer to the question for sorting: approximately $nlogn$ (Hoare, Quicksort). The complexity of 3-SAT is open, but widely conjectured to be exponential.

We can now restate the result of Hoare (Quicksort).

In Asymptotic analysis of algorithms, we saw how, given a certain sort of operation on a list of numbers, we could work out how many times that operation needs to be applied to sort the list. However, in general, we should like to be able to investigate the resource-intensiveness of computations for all sort of problems. In some cases, it is not obvious what the analogous operations should be. We shall now investigate a more general approach that allows us to deal with a considerably greater number of problems. We begin with a seemingly arbitrary model of computation, and then explain why it is not so arbitrary after all.

This seems quite arbitrary—

In general, we might therefore think that the putative runtime of an algorithm required to solve a problem varies too much with respect to the model of computation. However, one class of runtimes is highly robust to such changes.

Note that this definition is relative to a model of computation. However, it turns out that the class of problems that admit polynomial-time algorithms is robust with respect to all the worries above, i.e., changing any of those features does not change the class of problems for which there are polynomial-time algorithms.

Emde Boas (Models: § 1) puts it thus.

There exists a standard class of machine models…[that] simulate each other with polynomially bounded overhead…

This standard class corresponds, it is thought, to all ‘reasonable’ (Dean, Complexity: § 2.2) or physically realisable models of computation. The evidence for this is in effect that no convincing counterexamples have yet been found; it is somewhat analogous, therefore, to the Church–Turing thesis.

Our earlier conclusions (A model of computation) might be summarised as making the following conjecture: physically plausible models of computation do not differ in the problems they can solve in polynomial time.

What has this to do with language? To a certain extent, the argument must be reconstructed, but its rough outlines are clear.

A first premiss is the so-called Cobham–Edmonds thesis.

The Cobham–Edmonds thesis is only meaningful relative to a model of computation. But, if the van Emde Boas invariance thesis is correct, any reasonable model of computation will yield the same class of feasibly computable functions.

I shall, at this point, make a

The Cobham–Edmonds thesis might seem to admit obvious counterexamples. For instance, an algorithm that takes $\mathrm{\Theta }(n^{2^{100}})$ time seems obviously infeasible. (For that runtime to be meaningful, it would have to be associated with some privileged subset of the ‘reasonable’ machine-class above; a good example is e.g. physically instantiated computers.) Less obviously, there is some reason to suspect that some problems that likely have no polynomial-time algorithm are feasible. In this case, we might nevertheless hold that, most of the time, the Cobham–Edmonds thesis is correct. For instance, there are surprisingly few ‘galactic’ algorithms, i.e. algorithms with polynomial asymptotic runtime that in practice are unusable; see e.g. Helfgott (Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)), Helfgott (Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman, ...)), and Lipton and Regan (David Johnson). We can therefore provisionally take the Cobham–Edmonds thesis to be a (defeasible) heuristic in the sense above.

What has this to do with language or cognition? There are, broadly, I think, two sorts of argument that relate asymptotic analysis to language.

For the sake of argument, I will assume that these arguments are right, and that, therefore, ‘language computations’ are amenable to asymptotic analysis.

Is the application of asymptotic analysis to cognition and language an idealisation? First, I shall give an example of computational analysis that plausibly is not an idealisation.

Let us suppose, with Searle (Rediscovery: 200), that

[T]here [is] some description of the brain such that under that description you could do a computational simulation of the operations of the brain…given Church's thesis that anything that can be given a precise enough characterization as a set of steps can be simulated on a digital computer…in the same sense in which weather systems, the behavior of the New York stock market, or the pattern of airline flights over Latin American can.

Turing (Computability: § 11) showed that no Turing machine decides the Entscheidungsproblem. If we follow Searle’s rendering of Church’s thesis, it follows that the brain does not solve the Entscheidungsproblem either. I suggest there is no obvious idealisation here. (Of course, the argument might be false; but on its intended reading, it should be read as approximately false in the way idealisations usually are.) In other words, a fairly natural computationalist view is that these results from computability theory apply straightforwardly to computation generally, and, therefore, to cognition—and so to language computations.

However, in a considerable number of the arguments to follow, some antecedent assumptions seem to be false, and, therefore, the arguments will have to be parsed as idealisations. To say that the antecedent assumptions are false is not to deny computationalism. Suppose we are given a learning task over some stream of data $x_1,x_2,x_3,...$ (e.g. linguistic input). It may turn out that the probability distributions from which $x_1$ and $x_2$, for instance, are drawn are not independent. For simplicity, however we may assume that $x_1,...$ are i.i.d. variables; making this assumption, we may find some asymptotic bound on the learning task. There is nothing inherently objectionabfle about the i.i.d. assumption, but it must be assessed as an idealised antecedent assumption, in addition to the computational model of language computations supposed.

I shall take idealisation to be the ‘intentional introduction of distortion into scientific theories’ (Weisberg, Idealization: 639) (presumably with non-malicious intent). The accuracy or realism of an idealisation is not, per se, necessarily of interest. It might mislead as to the preidctive inaccuracy entailed by the idealisation (Friedman, Methodology: § III.)

One lesson to draw from that example is that the purpose of an idealisation matters. Weisberg (Idealization: § 1) distinguishes ‘Galilean’ and ‘minimalist’ idealisation. The former distorts theories to simplify them, for computational tractability—‘to get traction on the problem’ on pragmatic grounds. The latter construts and studies theoretical models containing only the ‘core causal factors which give rise to a phenomenon’. In general, idealisations’ purposes are representational ideals, e.g. (Weisberg, Idealization: § 2)

inclusion rules [which] tell the theorist which kinds of properties of the phenomenon [are] of interest[; and] fidelity rules [concerning] the degrees of precision and accuracy with which each part of the model is to be judged.

For instance, completeness requires inclusion of all the properties of the target phenomenon, anything external giving rise to those properties, and an analogue of any structural or causal relationship within the model, all with arbitrary accuracy and precision. Simplicity can e.g. serve pedagogical purposes, or show the minimal conditions required to generate some property. Isolating ‘only…the factors that made a difference’ can help us to formulate or analyse more complex models. Predictive accuracy may be practically useful. And so on.