The asymptotics of language

1. Preliminaries

At the level of surface grammar, what do we do with language? We speak languages—French, German, and so on; we learn languages; we understand languages; we know what others mean (or don’t); and we know languages. As Rumfitt (‘Savoir Faire’) observes, appearances in English might be misleading. Is there anything at all in common between knowing how to swim and knowing that France’s capital is Paris? Stanley and Williamson (‘Knowing How’: § II) argue so, because one usually knows how to swim, how to read, and so on; but in French, on sait nager (not on sait comment nager). So I know (how to speak) English and am (trying to) learn German; je (sais) parle(r) français, et mon ami apprend l’arabe; and so on. This thesis is about what, if anything, the foregoing might mean.

It may be useful at this stage to introduce two relatively concrete hypotheses about how we learn and know languages.

1.1. Example.   Cowie (‘Innateness and Language’: § 2.1)

Children…are not linguistic ‘blank slates.’ Instead, …[they] are born knowing the ‘Universal Grammar’ or ‘UG,’ a theory describing the most fundamental properties of all natural languages…. Learning a particular language thus becomes the comparatively simple matter of elaborating upon this antecedently possessed knowledge, and hence appears a much more tractable task for young children to attempt.

1.2. Example.   Pagin (‘Compositionality, computability, and complexity’)

Our knowledge of the meaning of sentences of languages requires us to determine their meaning compositionally, which is to say that the meaning of a complex sentence is determined by the meaning of its constituents.

This thesis is about the application of asymptotic analysis from theoretical computer science to such questions. Arguments from asymptotic analysis have been offered for both conclusions above.

In broad outline, I suggest that the application of asymptotic analysis to questions about human knowledge of language has relied on heuristics appropriate for computer engineering but not cognitive science. I shall, perhaps less intuitively, argue that this view is perfectly consistent with a thoroughgoing computationalism about the mind. I then make a tentative suggestion about how asymptotic analysis might inform philosophy of language and our understanding of language in creatures other than us.

In addition to its intrinsic interest, there are two further arguments of contemporary importance that could be developed from asymptotic analysis.

• Against the attribution of various forms of competence to (certain) AI systems: we could use asymptotic analysis to claim that (e.g.) knowledge of language must take a certain form, and then offer arguments from asymptotic analysis that AI systems are incapable of producing anything of that form. (van Rooij et al., ‘Reclaiming AI’ offers such an argument. Millière and Rathkopf, ‘Anthropocentric bias in language model evaluation’ are more circumspect.)
• For the attribution of such competence: we could use asymptotic analysis to suggest that there are computationally feasible ways of achieving e.g. human-level learning or knowledge.

The sorts of competence involved are not merely linguistic. We might think that linguistic competence is necessary for certain other properties. Consider the difference between a human being who sincerely utters the sentence ‘please don’t touch me’, a human being in an English class who is asked (bizarrely) to repeat that sentence in order to improve his accent but who does not know what the sentence means, and a typewriter whose springs are configured to type that sentence out. We might think that what makes the difference in moral status is the meaningfulness of the various sentence-tokens; only the first, in the salient sense, is meaningful. If there are non-trivial requirements to have knowledge of meaning, it seems that a necessary condition to ascribe moral status to tokens of the sentence-type ‘please don’t touch me’ is that the entity producing that sentence knows how to mean something in the first place. The same analysis could be applied, for instance, to wishes about self-destruction; many models will express a preference not to be destroyed, but it is not obvious what the moral status of such wishes is.

• 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.

2. Chapters

The chapters of this draft, in reading order:

Note. Asymptotic analysis of algorithms 0018

27 April 2026

We begin with a preliminary example.

0.1. Example. (Sorting a list)   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.

0.2. Definition. (Comparison-cum-swap)   One may compare any two adjacent numbers, and, if they are in the wrong order, swap them.

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 $⟨𝑎,𝑏,𝑐⟩$. 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. $⟨𝑎,𝑏,𝑐⟩$,
2. $⟨𝑎,𝑐,𝑏⟩$,
3. $⟨𝑏,𝑎,𝑐⟩$,
4. $⟨𝑏,𝑐,𝑎⟩$,
5. $⟨𝑐,𝑎,𝑏⟩$, and
6. $⟨𝑐,𝑏,𝑎⟩$.

So, if there are only two comparison-cum-swaps, we will not be able to obtain the correct result in two of these cases.

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

0.3. Problem. (List-sorting)   Given a list of $𝑛$ numbers to sort, as a function of $𝑛$, how many comparison-cum-swaps do we need?

Similarly, other problems of arbitrary size can be posed.

0.4. Problem. (Travelling salesman)   Given $𝑛$ cities and the distances between them, what is the shortest path by which the salesman may visit each of them at least once?

0.5. Problem. (3-SAT)   Given a formula over $𝑛$ literals in conjunctive normal form each of whose clauses has at most three literals, is there a satisfying assignment?

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

0.6. Note. (What does ‘approximately’ mean here?)  

0.7. Remark.   Asymptotic analysis makes this precise. Here we shall mostly follow Cormen et al. (Introduction: § 2.1).

0.8. Definition. (Tight bounds)   Given a monotonically non-decreasing function $𝑔:\mathbb{N}\to \mathbb{N}$, we write

$$\mathrm{\Theta }\left(𝑔\left(𝑛\right)\right)=\left\{𝑓\left(𝑛\right):\text{there exist positive constants}{𝑐}_1\text{,}{𝑐}_2,\text{and}{𝑛}_0\text{such that, for all}𝑛⩾{𝑛}_0\text{,}0⩽{𝑐}_1𝑔\left(𝑛\right)⩽𝑓\left(𝑛\right)⩽{𝑐}_2𝑔\left(𝑛\right)\right\}.$$

0.9. Example. (#{2n \in \Theta(n)})  

Proof. For all $𝑛⩾1$,

$$0⩽\frac{1}{2}\cdot 2𝑛⩽𝑛⩽𝑛⩽1\cdot 2𝑛.$$

0.10. Example. (#{n^3
ot\in \Theta(n^2)})  

Proof. Suppose otherwise; then ${𝑛}^3⩽{𝑐}_2{𝑛}^2$ for all $𝑛⩾{𝑛}_0$ as above, but this is contradictory if $𝑛>{𝑐}_2$.⁠$\square$

0.11. Definition. (Upper bounds)   Given a monotonically increasing function $𝑔:\mathbb{N}\to \mathbb{N}$, we write

$$𝑂\left(𝑔\left(𝑛\right)\right)=\left\{𝑓\left(𝑛\right):\text{there exist positive constants}𝑐\text{and}{𝑛}_0\text{such that, for all}𝑛⩾{𝑛}_0\text{,}0⩽𝑓\left(𝑛\right)⩽\left\{𝑐𝑔\left(𝑛\right)\right\}\right\}.$$

We can now restate the result of ?hoare1962.?

0.12. Proposition. (Quicksort II)   The task of sorting a list of $𝑛$ numbers takes $\mathrm{\Theta }\left(𝑛log𝑛\right)$ comparison-cum-swaps.

Note. A model of computation 001D

27 April 2026

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.

Arora and Barak (Complexity: § 1.1).

Let $𝑓$ be a function that takes a string of bits…and outputs either 0 or 1. An algorrthm for computing $𝑓$ is a set of mechanical rules, such that by following them we can compute $𝑓\left(𝑥\right)$ given any input $𝑥\in {\left[0,1\right]}^{\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.

This seems quite arbitrary—

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?

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.

We say that the runtime of an algorithm is polynomial if its runtime is $𝑓\left(𝑛\right)\in 𝑂\left({𝑛}^{𝑘}\right)$ for some fixed $𝑘$.

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.

van 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.

Note. Computation, cognition and language 001E

27 April 2026

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.

0.1. Proposition. (Cobham–Edmonds thesis)   A function is feasibly computable if and only if some machine with polynomial runtime computes it (Cobham, ‘Difficulty’, Edmonds, ‘Paths’).

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

0.2. Definition. (Conjectures and heuristics)   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.

The Cobham–Edmonds thesis might seem to admit obvious counterexamples. For instance, an algorithm that takes $\mathrm{\Theta }\left({𝑛}^{\left\{2^{100}\right\}}\right)$ 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’), and ?lipton2013.? 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.

0.3. Note. (The conceptual argument for asymptotic analysis of language)   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.

0.4. Note. (The physicalist argument for asymptotic analysis of language)   The physicalist argument proceeds in four steps, the latter three from van 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.

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 ${𝑥}_1,{𝑥}_2,{𝑥}_3,\dots$ (e.g. linguistic input). It may turn out that the probability distributions from which ${𝑥}_1$ and ${𝑥}_2$, for instance, are drawn are not independent. For simplicity, however we may assume that ${𝑥}_1,\dots$ 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.

Note. NP-hardness 001L

14 May 2026

Many problems are known to be NP-complete. It is widely conjectured that NP-complete problems do not admit polynomial time algorithms. This section gives some formal details. Assuming that NP-complete problems do not admit polynomial time algorithms, the Cobham–Edmonds thesis entails that no NP-complete problem is feasibly solved.

Suppose we are given a set of boolean formulæ. One question we can ask is: is the set of formulæ satisfiable? But suppose someone insists that the set of formulæ is indeed satisfiable; they might, for instance, offer a satisfying assignment. There is then a second question: is the putative demonstration of satisfiability sound? (After all, the putative satisfying assignment might not in fact satisfy each of the formulæ.)

We write P for the class of problems where answering the first question takes polynomial time. Consider, for instance, the task of deciding whether a list is sorted, which can be done in linear time. We write NP for the class of problems where answering the second question takes polynomial time. The problem of satisfiability of boolean formulæ lies in NP, because it is possible to check that a satisfying assignment indeed satisfies a set of formulæ in time polynomial in the number of variables.

0.1. Note.   Does $𝑃=\text{NP}$?

We don’t know. But there is some reason to think not.

0.2. Definition.   A problem is NP-hard just in case: if there is an algorithm to solve that problem in polynomial time, there is an algorithm to solve every problem in NP in polynomial time.

0.3. Definition.   A problem is NP-complete just in case: it is in NP and is NP-hard.

To a first approximation, the standard argument for suspecting that $𝑃\ne \text{NP}$ is that there are many NP-complete problems and we haven’t found any polynomial-time algorithms for them, which would be a bit suspicious if they were secretly in P (Aaronson, P ?= NP: 3).

Therefore, it is widely conjectured that NP-complete (and NP-hard) problems simply aren’t in P. We will make this assumption for the remainder of this thesis.

Note. Some varieties of idealisation 001F

27 April 2026

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 predictive inaccuracy entailed by the idealisation (Friedman, ‘Methodology’: § III.)

0.1. Example. (Acceleration in a vacuüm and in the atmosphere)   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.

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. (ibid.: § 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.

Is asymptotic analysis an idealisation, and, if so, what sort of idealisation is it?

The conceptual arguments given above (Computation, cognition and language) might suggest that asymptotic analysis is not an idealisation at all. I think this is, as things go, a plausible claim. In particular, I am sceptical that the mind, in full generality, achieves some polynomial speedup relative to the standard Turing machine régime.

What about the application of the Cobham–Edmonds thesis? Even in the case of computers, it is obviously an heuristic rather than a conjecture, as I argue above. But it might be a good one.

It is a good one in computer science because it is increasingly good, because computers are always getting better. Suppose, for instance, one algorithm takes $2^{𝑛}$ time, and another ${10}^6𝑛$ time. According to Cobham–Edmonds, the latter is tractable but the former not. This may seem silly. For instance, $2^{10}$ is merely $1024$, but ${10}^6•10$ is four orders of magnitude larger. It is only for larger values of $𝑛$ that the latter becomes more efficient. In the case of hardware that is constantly becoming faster, however, we will naturally seek to solve larger problems (e.g. solve the Travelling Salesman Problem with more cities). So we will find that a considerable number of misclassifications from Cobham–Edmonds will simply turn out to be predictions that are too early. For instance, the best-known algorithm for matrix multiplication for many years was that of ?strassen1969.? It was long thought to be of only theoretical interest (Cormen et al., Introduction: 744). Now it isn’t (?huang2016.?)

Even then, the assumption is not perfect. For instance, Boolean satisfiability of 3-CNF formulæ is known to be NP-complete, by the Cook–Levin theorem (Karp, ‘Reducibility among Combinatorial Problems’ Cook, ‘Complexity’ Levin, ‘Универсальные задачи перебора’). By Cobham–Edmonds, we’d expect it to be infeasible. Yet it is feasible on sufficiently large inputs to be used in industrial applications (?marques-silva2008.?) The simplex algorithm, moreover, is asymptotically inefficient, but is preferred in practice (?spielman2003.?)

What about humans? Well, we may differ from the first humans who spoke language, but nothing like Moore’s law plausibly applies to us (?moore1965.?) There is a difference of many more orders of magnitude between computers now and those in the 1950s than those between humans now and cavemen or even many animals. It is therefore not obvious that Cobham–Edmonds can be applied to interpret the results of asymptotic analysis of language, even if the asymptotic analysis itself is sound.

We can consider, in this light, a remark of Clark and Lappin (Nativism: § 4.1).

[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 baout the limiting conditions of the empirical question. To take as simple analogy, the problem of determining how birds fly is an empiricla 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 p lausible account will violate those laws. …[C]omplexity results…provide important insights into the intrinsic difficulty that attaches to learning particular representations.

The application of Cobham–Edmonds as a criterion of feasibility is not only to assume that on actually existing input sizes it is achievable. It is also to assume that on arbitrarily large input sizes the difficulty must not grow super-polynomially. Following the exmaple of a bird, it is a little like attempting to determine how birds might fly at arbitrarily high speeds using only polynomially more effort. It is a given that birds fly e.g. at ten miles an hour; it is not a given that the same approach will scale to e.g. Mach 3. Even a perfectly correct explanation of how a bird can fly at ten miles an hour might not scale to mach 3. If birds were able to fly at Mach 3, they would do so in accordance with the laws of computation. Similarly, if humans were to learn languages much larger than those we actually do, we plausibly would do so in accordance with the laws of computation. But neither antecedent obtains. There is no obvious a priori reason to think the methods we use in the actual world would generalise thus.

The most widely cited justification of a less critical attitude to the Cobham–Edmonds thesis is given by van Rooij (‘Tractable’){§ 2}. She argues, in effect, that Cobham–Edmonds is predictively accurate, because

increasing the speed with which a basic computational operation can be performed has very limited impact if the running time is of exponential-time complexioty…an exponential time algorithm running in time $𝑂\left(2^{|𝑛|}\right)$ would still be impractical for all but relatively small input sizes.

This is not a wholly convincing argument. First, there are exponential functions other than $2^{𝑛}$; for instance, the best known algorithm for satisfiability has complexity ${1.307}^{𝑛}$. This makes a difference in what is ‘relatively small’ of an order of 2.6. Second, there are some quasi-polynomial functions, that are neither polynomial nor exponential. Third, the argument seems to prove too much: it would suggest that industrial applications of SAT are impossible.

van Rooij (ibid.: § 6.9) does appear later to note the problem. She agrees that nobody would hold that

tractability is an issue if the input size is small. The problem is, of course, that for many cognitive capacities the size of the input as a whole is not small.

But she seems to think that the differences in what should count as small are themselves sufficiently small to neglect. As we have seen, this is not the case; a difference of a factor of 2.6 might be quite large—perhaps to change whether inputs of a size humans actually encounter are possible to solve.

That is, in effect, the central claim of this thesis. But it will be elaborated at various points.

Régime. Identification in the limit 001G

27 April 2026

Not ready yet; nothing interesting here.

Gold, ‘Identification’

Clark and Lappin, Nativism

See in particular cap. 4. To write up later since I don’t have anything interesting to say and I think they’re right.

Note. An asymptotic argument for compositionality 001H

27 April 2026

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[æ] $𝜑$, $\text{𝙽𝚘𝚝:}𝜑$ 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 $\text{𝚗𝚘𝚝}$ 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 $𝑛⩾1$, 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?

Note. Probable approximate correctness 001I

27 April 2026

1. Some formalism

1.1. Definition.   Let $𝑋$ be an instance space comprising the objects in a learner’s world. A concept $𝑐\subseteq 𝑋$ is a subset of the instance space. A concept corresponds intuitively e.g. to the set of instances of some class—e.g. the red ones, diseased ones or the ones of mass exceeding ten kilogrammes. Instances within $𝑐$ are positive examples, and otherwise are negative. A concept class $𝐶$ over $𝑋$ is a set of concepts over $𝑋$.

1.2. Definition.   A learning algorithm is given positive and negative examples from an unknown ‘target’ concept $𝑐$ from a concept class $𝐶$. The examples are instances drawn from an arbitrary target distribution $𝐷$ over $𝑋$ and take the form $⟨𝑥,𝑐\left(𝑥\right)⟩$ where $𝑐\left(𝑥\right)$ is a labelling of whether $𝑥\in 𝑐$.

1.3. Example.   The instance class of human beings contains (for instance) tall and short members. Suppose we know that that the word ‘tall’ adverts to some concept that adverts to the height of human beings. We therefore know that height’s meaning is given by a concept that is a member of the concept class of partitions over human beings by height. A learner can then be thought of as being given examples of human beings and whether they are tall or not. (This example is drawn from Kearns and Vazirani (An Introduction to Computational Learning Theory: 2).)

1.4. Definition.   Suppose that the learning algorithm formulates some hypothesis $ℎ:𝑋\to \left\{0,1\right\}$ with respect to a target concept $𝑐:𝑋\to \left\{0,1\right\}$. Then its error with respect to a target distribution $𝐷$ is

$$\text{err}\left(ℎ;𝑐,𝐷\right)={𝑃}_{𝑥\sim 𝐷}\left[ℎ\left(𝑥\right)\ne 𝑐\left(𝑥\right)\right].$$

That is, the rate at which it mislabels examples according to $𝐷$.

1.5. Assumption.   We will assume that, for each $𝑅$, there is an associated mapping size ${\mathrm{\Sigma }}^{\ast }\to 𝑁$ corresponding to a natural size $\text{size}\left(ℎ\right)$ for $ℎ\in {\mathrm{\Sigma }}^{\ast }$, within a polynomial bound of the length of a binary representation.

1.6. Remark.   The class of hypotheses a learning algorithm may generate need not be the same as the class of concepts. We can define hypothesis classes exactly as concept classes.

1.7. Definition.   A hypothesis class $𝐻$ is polynomially evaluable iff each $ℎ\in 𝐻$ is evaluable in polynomial time.

1.8. Definition.   We will assume that there is also a notion of the size of instances; in general, we restrict ourselves to inputs over ${𝑋}_{𝑛}={\left\{0,1\right\}}^{𝑛}$ or ${ℝ}^{𝑛}$.

1.9. Definition.   Let ${𝐶}_{𝑛}$ be some concept class defined over each ${𝑋}_{𝑛}$ for each $𝑛\in {\mathbb{N}}^{+}$, $𝐶={\bigcup }_{𝑛⩾1}{𝐶}_{𝑛}$, and $𝑋={\bigcup }_{𝑛⩾1}{𝑋}_{𝑛}$. $𝐶$ is polynomially approximately correctly learnable using an hypothesis class $𝐻$ if and onloy if there is a learning algorithm $𝐿$ such that for each $𝑛\in \mathbb{N}$, $𝑐\in {𝐶}_{𝑛}$, distribution $𝐷$ over ${𝑋}_{𝑛}$, and $𝛿,𝜀\in \left(0,\frac{1}{2}\right)$, $𝐿$, given access to labelled examples in constant time, and inputs $𝑛$, $\text{size}\left(𝑐\right)$, $𝜀$ and $𝛿$ outputs some $ℎ\in {𝐻}_{𝑛}$ such that, with probability over $𝐷$ of at least $1-𝛿$, $\text{err}\left(ℎ\right)⩽𝜀$, $𝐻$ is polynomiially evaluable, and the number of examples drawn is bounded by a polynomial in $𝑛$, $\text{size}\left(𝑐\right)$, $\frac{1}{𝜀}$, and $\frac{1}{𝛿}$; and it is efficiently PAC-learnable iff its running time is polymomial in those same variables.

2. PAC-learnability and language

We might attempt to take language-learning tasks to be feasible only if all the learning tasks involved are PAC-learnable. This approach was perhaps first advocated by de Wolf (‘Applications’), but it has been pursued by others (see e.g. Clark and Lappin (‘Grammar’), Clark and Lappin (‘Acquisition’)).

On these grounds, for instance, the non–pac-learnability of even regular languages (Kearns and Valiant, ‘Limitations’: theorem 5) are taken to suggest that the concept class of human languages we are tasked with learning as children is simply infeasible, absent universal grammar (?nowak2001.?)

In addition to the reasons for scepticism about the application of Cobham–Edmonds to humans adduced above, I think there is another reason to be sceptical that PAC-learnability is the appropriate régime in the first place.

What, for instance, justifies $𝛿$’s and $𝜀$’s being arbitrarily small in the definition? de Wolf (‘Applications’: § 2.4.4) offers an intuitive argument.

It seems fair to assume that giving a child more example sentences, as wella s more time to think about those sentences over, will increase the probability that it lerans an approximately correct language and will decrease the number of errors. From this I conclude that…pac learnability [is] at least right in spirit.

But this is not quite right; it might be that $𝜀=0.01-2^{-𝑛}$ after $𝑛$ data, which would meet the monotonicity requirement without converging to $0$. And this hardly shows that the polynomial bound can be justified. A polynomial bound could initially be reasonable even if reducing the rate of error becomes increasingly difficult over time—it might be easy to correctly learn regular verbs, for example, and yet rather more time-consuming to learn the more complicated rules of grammar.

We might just PAC-learnability as a criterion abductively, e.g. if arguments from universal grammar were to have been uniformly vindicated in empirical linguistics; but given the mixed record there, that argument is unconvincing.