Computation, cognition and language

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.