Draft. The asymptotics of language [0017]

  • 27 April 2026

1. Preliminaries

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.

Note 2. Asymptotic analysis of algorithms [0018]

  • 27 April 2026

We begin with a preliminary example.

Example 2.1. 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.

Operation 2.1.1. 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 ⟨a,b,c⟩. So if there are two comparison-cum-swaps, there are at most 2×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⟩.
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.

Problem 2.1.2. List-sorting

Given a list of n numbers to sort, as a function of n, how many comparison-cum-swaps do we need?

Similarly, other problems of arbitrary size can be posed.

Problem 2.2. Travelling salesman

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?

Problem 2.3. 3-SAT

Given a formula over n 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 nlogn (Hoare, Quicksort). The complexity of 3-SAT is open, but widely conjectured to be exponential.

Question 2.4. What does ‘approximately’ mean here?

Answer. 

Asymptotic analysis makes this precise. Here we shall mostly follow Cormen, Leiserson and Rivest (Introduction: § 2.1).

Definition 2.5. Tight bounds

Given a monotonically non-decreasing function g:ℕ→ℕ, we write Θ(g(n))={f(n):there exist positive constants c1, c2, and n0 such that, for all n⩾n0, 0⩽c1g(n)⩽f(n)⩽c2g(n)}.

Example 2.6. 2n∈Θ(n)

Proof. 

For all n⩾1, 0⩽12·2n⩽n⩽n⩽1·2n.

Example 2.7. n3∉Θ(n2)

Proof. 

Suppose otherwise; then n3⩽c2n2 for all n⩾n0 as above, but this is contradictory if n>c2.

Definition 2.8. Upper bounds

Given a monotonically increasing function g:ℕ→ℕ, we write O(g(n))={f(n):there exist positive constants c and n0 such that, for all n⩾n0, 0⩽f(n)⩽cg(n)}.

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

Proposition 2.9. Quicksort II

The task of sorting a list of n numbers takes Θ(nlogn) comparison-cum-swaps.

Note 3. 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.

Definition 3.1. Turing machines (informal) [0019]

  • 27 April 2026

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∈[0,1]∗. 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—

3.2. Worries about Turing machines [001B]

  • 27 April 2026
  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.

Definition 3.3. Polynomial time [001C]

  • 27 April 2026

We say that the runtime of an algorithm is polynomial if its runtime is f(n)∈O(nk) for some fixed k.

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.

Note 4. 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.

Claim 4.1. 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

Distinction 4.2. 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 Θ(n2100) 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.

Argument 4.3. 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.

Argument 4.4. The physicalist argument for asymptotic analysis of language

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.

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 x1,x2,x3,... (e.g. linguistic input). It may turn out that the probability distributions from which x1 and x2, for instance, are drawn are not independent. For simplicity, however we may assume that x1,... 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 5. 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 preidctive inaccuracy entailed by the idealisation (Friedman, Methodology: § III.)

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

6. Identification in the limit [001G]

  • 27 April 2026

7. An asymptotic argument for compositionality [001H]

  • 27 April 2026

Reference 7.1. Compositionality, computability, and complexity [pagin2021]

Definition 7.1.1. Grammatical term algebra (§ 2.1) [pagin2021-gta]

A grammatical term algebra GTAL of a language L is a partial algebra ⟨GTL,ATL,ΣL⟩, where—

  1. GTL is the set of grammatical terms for L,
  2. ATL is a finite set of atomic (grammatical) terms for L, and
  3. ΣL is a finite set of syntactic operations for L. GTL is the closure of ATL under ΣL.

Definition 7.1.2. Meaning operations (§ 2.2) [pagin2021-meaning-operation]

A meaning operation r over a domain of meanings M is some function Mn→M.

Definition 7.1.3. Semantic functions (§ 2.2) [pagin2021-semantic-function]

Where GTAL is a grammatical term algebra and M is a domain of meanings, any μ:GTL→M is a semantic function.

Definition 7.1.4. Standard compositionality (§ 2.2) [pagin2021-standard-compositionality]

Given a grammatical term algebra GTAL and domain M of meanings, a semantic function μ:GTL→M is standard compositional iff for every n-ary operation σ∈ΣL there is a meaning operation rσ:Mn→M such that for any t1,...,tn∈Domσ⊆GTL, μ(σ(t1,...,tn))=rσ(μ(t1),...,μ(tn)).

Definition 7.1.5. General compositionality (§ 2.3) [pagin2021-general-compositionality]

A semantic system S is general compositional iff for every n-ary operation σ∈ΣL and every member μi∈S′ there is a meaning operation Mn→M such that for any grammatical terms t1,...,tn∈Domσ μi(σ(t1,...,tn))=rσ,i(μj1(t1),...,μjn(tn)), where for 1⩽k⩽n μjk=ΦS(μi,σ,k).

Definition 7.1.6. Meaning algebras (§ 3) [pagin2021-meaning-algebra]

A meaning algebra over a set of meanings M is a triple MAM=⟨M,BM,RM⟩, where—

  1. BM is a finite set of basic meanings,
  2. RM is a finite set of elementary meaning operations,
  3. M closes BM under RM, and
  4. for all δ,δ′∈RM and x1,...xn,y1,...,ym, δ(x1,...,xn)∉BM and, if δ(x1,...,xn)=δ′(y1,...,ym) then δ=δ′, m=n, and xi=yi for 1⩽i⩽n.

Definition 7.1.7. Semantic systems (§ 3) [pagin2021-semantic-system]

Given a grammatical term algebra GTAL and domain M of meanings, a semantic system S is a triple ⟨S′,μS,ΦS⟩ where—

  1. S′ is a finite set of semantic functions μj:GTL→M, μS∈S, and
  2. ΦS:S′×ΣL×N→S′ is a partial selection function.

Given some semantic function μj and a syntactic operation σ, ΦS then gives another semantic function μk for each nth-position term.

Finally, S(t)=μS(t).

Definition 7.1.8. Semantic algebras (§ 3) [pagin2021-semantic-algebra]

A semantic algebra over a language L and domain M of meanings is a triple SALM=⟨⟨GTL,M⟩,⟨ATL,BM⟩,⟨ΣL,RM⟩⟩ where—

  1. ⟨GTL,ATL,ΣL⟩ is a grammatical term algebra for L, and
  2. ⟨M,BM,RM⟩ is a meaning algebra for M.

Definition 7.1.9. Size (§ 5) [pagin2021-size]

The size of a term is the number of atoms and operators contained within it.

Definition 7.1.10. Input terms (§ 5) [pagin2021-input-terms]

The input terms of a rewriting system are of the form ‘μ(t)’ where t is a syntactic term.

Definition 7.1.11. Input complexity (§ 5) [pagin2021-input-complexity]

Let s be a normal term.

The term complexity CtR(s) of s relative to R is the length of the shortest derivation from some input term μ(t) to s.

The input complexity CRi(k) is the maximal CtR(s) where s has size k.

Definition 7.1.12. Term rewrite systems (§ 6.1) [pagin2021-trs]

A term rewrite system (TRS) Φ is a pair ⟨ΣΦ,RΦ⟩ where—

  1. ΣΦ is a signature comprising a finite set of n-ary operators (including nullary constants), and
  2. RΦ is a set of reductions over the set TΦ of terms over ΣΦ.

We will write t1→Φt2 (omitting the subscript where context makes it obvious) when the application of some rule r∈RΦ yields the contractum t2.

A sequence of applications t1→t2→...→tn is a derivation. We write t1→Φ+tn where →Φ+ is the transitive closure of →.

Definition 7.1.12.1. Conditional term rewrite systems (§ 6.1) [pagin2021-ctrs]

In a conditional term rewrite system ΣΦ,RΦ, the reductions are conditioned over some conditions C1,...,Cn.

Definition 7.1.12.2. Many-sorted term rewrite systems (§ 6.1) [pagin2021-many-sorted-trs]

In a many-sorted term rewrite system, TPsi is partitioned into subsets corresponding to sorts, and argument places for operators have sort restrictions; complex terms whose subterms satisfy the sort restrictions are well-sorted (corresponding to grammaticality).

Definition 7.1.12.3. Normal form (§ 6.1) [pagin2021-normal-form]

A term that cannot be reduced further is in normal form.

Definition 7.1.12.4. Termination (§ 6.1) [pagin2021-terminate]

If every derivation leads to a term in normal form, a system terminates.

Definition 7.1.12.5. Confluence (§ 6.1) [pagin2021-confluence]

Φ is confluent iff, for all terms t1,t2,t3, whenever t1→Φ+t2 and t1→Φ+t3, there is some t4 such that t2→Φ+t4 and t3→Φ+t4.

Definition 7.1.12.6. Convergence (§ 6.1) [pagin2021-convergence]

A confluent system that terminates is convergent.

Definition 7.1.13. μ-systems (§ 6.1) [pagin2021-mu-system]

A μ-system is a pair Φ=⟨ΣΦ,RΦ⟩ where—

  1. Σ=⟨Σo,Σm⟩ (an object- and meta-language signature),
  2. Σo=⟨Ao,Σo′⟩ where Ao is a set of atomic terms and Σ′ is a set of n-ary syntactic operators, so that the closure To of AO under Σ′ yields the grammatical term algebra ⟨TO,AO,ΣO′⟩ of OL,
  3. Σm=⟨Am,Σm′,S,F,G⟩ where—
    1. Am is a nonempty set of atomic meta-language expressions,
    2. Σm′ is a nonempty set of meta-language syntactic operators,
    3. S is a nonempty set of elementary meta-language function symbols,
    4. F is a possibly empty set of meta-language recursive function symbols over object language terms, and
    5. G is a possibly empty set of meta-language recursive function symbols over meta-language terms.

Remark 7.1.13.1. 

The canonical expressions of ML, Cm, close Am under Σm′, canonically express meanings, do not contain any μ operators or F/G functors, and rewrite derivations terminate with them.

Remark 7.1.13.2. 

The set S of the semantic vocabulary of Φ contains at least the semantic function symbol μ and is finite.

Remark 7.1.13.3. 

The set S(To) of μ-terms is the set of input terms to derivations, given by applying a semantic function symbol to an OL term.

Remark 7.1.13.4. 

F and G contain additional function symbols do not represent semantic functions, are not inputs to any rules in RΦ, but can take arguments from TO, S(To), and Cm.

Remark 7.1.13.5. 

The set Tm of meta-linguistic terms of ΣM is the closure of Am∪To under Σm′∪S∪F∪G.

Definition 7.1.14. Complex indirect constant μ-systems (§ 8.3.4) [pagin2021-CIC]

A complex indirect constant μ-system Φ must satisfy the following.

  1. RΦ is finite.
  2. For any rule, the rewrite variables on the rhs must be a subset of those on the left.
  3. Rewrite variables v1,v2,... take all and only object language grammatical terms as instances.
  4. Rewrite variables y1,y2,... take all and only expressions in Cm as instances.
  5. Every atomic rule r∈RΦ is of the form μi(t)→e where μi∈S, t∈AO and e is a simple or complex expression in Cm.
  6. For every pair ⟨μi∈S,t∈Ao⟩ there is an atomic rule.
  7. Every direct complex rule r has the form μi(α(v1,...,vn))→K(μk1(v1),...,μkn(vn))⇐Gr(α(v1,...,vn)) where Gr corresponds to grammaticality.
  8. Every indirect complex rule has the form μi(α(v1,...,vn))→f(μk1(v1),...,μkn(vn),v1,...,vn)⇐Gr(α(v1,...,vn)) where v1,...,vn are optional and f∈F.
  9. For every pair ⟨μi∈S,α∈Σo′, there is a unique complex (indirect or direct) rule.
  10. Every indirect ground rule is of the F-form f(y1,...,yn,...,tn)→K′(f′(y1,...,yn)) or the G-form g(e1,...,en)→K(e1,...,en) where f,f′∈F, g∈G, K,K′ are operators over Σm′, e1,...,en∈Am and t1,...,tj∈Ao, and at most one of the primed operators is null.
  11. Every indirect recurisve rule in RΦ has an F-form f(y1,...,yn,σ(v1,...,vn))→K(f(y1,...,yn,v1)...,f(y1,...,yn,vn)) or G-form g(K(y1,...,yn))→K′(g′(y1,...,yn)) where f∈F, g,g′∈G, K,K′ are operators over Σm′, σ∈ΣO′, and at most one of the primed operators is null.

Proposition 7.1.15.  [pagin2021-cic-terminate]

Complex indirect constant systems are convergent (§ 8.3.4).

Corollary 7.1.16.  [pagin2021-mdl]

Given a complex indirect constant μ-system, for any term t, there is some minimum derivation length to a unique normal form.

Proposition 7.1.17.  [pagin2021-general]

Let Φ be any complex indirect constant μ-system satisfying the following.

  1. For every n⩾1, there are object-language atoms a1,...an∈Ao such that for every 1⩽k⩽n, where t1=α1 and tk+1=δ(αk+1,tk), for some canonical expression e∈Cm, μ(tk)→Φ+e, and tk∈To.
  2. The complex rule for μ,δ is μ(δ(v1,v2))→f(μ(v1),μ(v2),v2)⇐Gr(d(v1,v2)).
  3. There are rules f(y1,y2,δ(v1,v2))→K(f(y1,y2,v1),f(y1,y2,v2)) and f(y1,y2,α)→Kα(y1,y2) for each α∈Ao.

Then Φ is intractable.

Lemma 7.1.17.1. 

Fix some k⩾1 and α1,...,αk. Define F(t):=f(μ(αk+1,μ(tk),t′)).

Moreover, define l(t) as the number of atomic leaves of t.

For every object-language subterm t of tk, T(F(t))⩾l(t)·T(μ(tk)).

Proof. 

By structural induction on t.

If t=α∈AO, F(α) has subterm μ(tk), which must be reduced to eliminate m to obtain a canonical form. Moreover, there is only one atomic leaf. So T(F(a))⩾T(μ(tk))=1·T(μ(tk)).

Suppose t=δ(t1,t2). Normalisation requires elimination of the root f of F(t). Since the third argument has head δ, only f(y1,y2,δ(v1,v2))→K(f(y1,y2,v1),f(y1,y2,v2)) will do so. Every derivation (minimum-length or otherwise) will have to apply that rule at some point. Without loss of generality, apply it at the beginning. Then F(t)→K(F(t1),F(t2)). Note K is terminal by definition of complex indirect constant μ-systems. So T(F(t))=1+T(F(t1))+T(F(t2))⩾l(t1)·T(μ(tk))+l(t2)·T(μ(tk))=l(t)·T(μ(tk)).

Proof. 7.1.17.2. 

Now consider a minimum-length derivation of μ(tk+1). There is some minimum-length derivation that begins μ(tk+1)→F(tk) whence T(μ(tk+1))=1+T(F(tk))⩾k·T(μ(tk)) whence T(μ(tn))⩾(n−1)!.

References

    Reference. Computational Complexity Theory [dean2021]

    Reference. Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis [vanrooij2019]

    Reference. Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman, ...) [helfgott2019]

    Reference. Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...) [helfgott2017]

    Reference. David Johnson: Galactic Algorithms [lipton2013]

    Reference. Linguistic nativism and the poverty of the stimulus [clark2011]

    Reference. Computational Complexity: A Modern Approach [arora2009]

    Reference. The Methodology of Positive Economics [friedman2007]

    Reference. Three Kinds of Idealization [weisberg2007]

    Reference. The language complexity game [ristad1993]

    Reference. The Rediscovery of the Mind [searle1992]

    Reference. Machine models and simulations [vanemdeboas1991]

    Reference. Introduction to algorithms [cormen1990]

    Reference. Paths, Trees, and Flowers [edmonds1965]

    Reference. The Intrinsic Computational Difficulty of Functions [cobham1965]

    Reference. Quicksort [hoare1962]

    Reference. Computability and λ-definability [turing1937a]

    Related

      An asymptotic argument for compositionality [001H]

      • 27 April 2026

      Reference. Compositionality, computability, and complexity [pagin2021]

      Definition. Grammatical term algebra (§ 2.1) [pagin2021-gta]

      A grammatical term algebra GTAL of a language L is a partial algebra ⟨GTL,ATL,ΣL⟩, where—

      1. GTL is the set of grammatical terms for L,
      2. ATL is a finite set of atomic (grammatical) terms for L, and
      3. ΣL is a finite set of syntactic operations for L. GTL is the closure of ATL under ΣL.

      Definition. Meaning operations (§ 2.2) [pagin2021-meaning-operation]

      A meaning operation r over a domain of meanings M is some function Mn→M.

      Definition. Semantic functions (§ 2.2) [pagin2021-semantic-function]

      Where GTAL is a grammatical term algebra and M is a domain of meanings, any μ:GTL→M is a semantic function.

      Definition. Standard compositionality (§ 2.2) [pagin2021-standard-compositionality]

      Given a grammatical term algebra GTAL and domain M of meanings, a semantic function μ:GTL→M is standard compositional iff for every n-ary operation σ∈ΣL there is a meaning operation rσ:Mn→M such that for any t1,...,tn∈Domσ⊆GTL, μ(σ(t1,...,tn))=rσ(μ(t1),...,μ(tn)).

      Definition. General compositionality (§ 2.3) [pagin2021-general-compositionality]

      A semantic system S is general compositional iff for every n-ary operation σ∈ΣL and every member μi∈S′ there is a meaning operation Mn→M such that for any grammatical terms t1,...,tn∈Domσ μi(σ(t1,...,tn))=rσ,i(μj1(t1),...,μjn(tn)), where for 1⩽k⩽n μjk=ΦS(μi,σ,k).

      Definition. Meaning algebras (§ 3) [pagin2021-meaning-algebra]

      A meaning algebra over a set of meanings M is a triple MAM=⟨M,BM,RM⟩, where—

      1. BM is a finite set of basic meanings,
      2. RM is a finite set of elementary meaning operations,
      3. M closes BM under RM, and
      4. for all δ,δ′∈RM and x1,...xn,y1,...,ym, δ(x1,...,xn)∉BM and, if δ(x1,...,xn)=δ′(y1,...,ym) then δ=δ′, m=n, and xi=yi for 1⩽i⩽n.

      Definition. Semantic systems (§ 3) [pagin2021-semantic-system]

      Given a grammatical term algebra GTAL and domain M of meanings, a semantic system S is a triple ⟨S′,μS,ΦS⟩ where—

      1. S′ is a finite set of semantic functions μj:GTL→M, μS∈S, and
      2. ΦS:S′×ΣL×N→S′ is a partial selection function.

      Given some semantic function μj and a syntactic operation σ, ΦS then gives another semantic function μk for each nth-position term.

      Finally, S(t)=μS(t).

      Definition. Semantic algebras (§ 3) [pagin2021-semantic-algebra]

      A semantic algebra over a language L and domain M of meanings is a triple SALM=⟨⟨GTL,M⟩,⟨ATL,BM⟩,⟨ΣL,RM⟩⟩ where—

      1. ⟨GTL,ATL,ΣL⟩ is a grammatical term algebra for L, and
      2. ⟨M,BM,RM⟩ is a meaning algebra for M.

      Definition. Size (§ 5) [pagin2021-size]

      The size of a term is the number of atoms and operators contained within it.

      Definition. Input terms (§ 5) [pagin2021-input-terms]

      The input terms of a rewriting system are of the form ‘μ(t)’ where t is a syntactic term.

      Definition. Input complexity (§ 5) [pagin2021-input-complexity]

      Let s be a normal term.

      The term complexity CtR(s) of s relative to R is the length of the shortest derivation from some input term μ(t) to s.

      The input complexity CRi(k) is the maximal CtR(s) where s has size k.

      Definition. Term rewrite systems (§ 6.1) [pagin2021-trs]

      A term rewrite system (TRS) Φ is a pair ⟨ΣΦ,RΦ⟩ where—

      1. ΣΦ is a signature comprising a finite set of n-ary operators (including nullary constants), and
      2. RΦ is a set of reductions over the set TΦ of terms over ΣΦ.

      We will write t1→Φt2 (omitting the subscript where context makes it obvious) when the application of some rule r∈RΦ yields the contractum t2.

      A sequence of applications t1→t2→...→tn is a derivation. We write t1→Φ+tn where →Φ+ is the transitive closure of →.

      Definition. Conditional term rewrite systems (§ 6.1) [pagin2021-ctrs]

      In a conditional term rewrite system ΣΦ,RΦ, the reductions are conditioned over some conditions C1,...,Cn.

      Definition. Many-sorted term rewrite systems (§ 6.1) [pagin2021-many-sorted-trs]

      In a many-sorted term rewrite system, TPsi is partitioned into subsets corresponding to sorts, and argument places for operators have sort restrictions; complex terms whose subterms satisfy the sort restrictions are well-sorted (corresponding to grammaticality).

      Definition. Normal form (§ 6.1) [pagin2021-normal-form]

      A term that cannot be reduced further is in normal form.

      Definition. Termination (§ 6.1) [pagin2021-terminate]

      If every derivation leads to a term in normal form, a system terminates.

      Definition. Confluence (§ 6.1) [pagin2021-confluence]

      Φ is confluent iff, for all terms t1,t2,t3, whenever t1→Φ+t2 and t1→Φ+t3, there is some t4 such that t2→Φ+t4 and t3→Φ+t4.

      Definition. Convergence (§ 6.1) [pagin2021-convergence]

      A confluent system that terminates is convergent.

      Definition. μ-systems (§ 6.1) [pagin2021-mu-system]

      A μ-system is a pair Φ=⟨ΣΦ,RΦ⟩ where—

      1. Σ=⟨Σo,Σm⟩ (an object- and meta-language signature),
      2. Σo=⟨Ao,Σo′⟩ where Ao is a set of atomic terms and Σ′ is a set of n-ary syntactic operators, so that the closure To of AO under Σ′ yields the grammatical term algebra ⟨TO,AO,ΣO′⟩ of OL,
      3. Σm=⟨Am,Σm′,S,F,G⟩ where—
        1. Am is a nonempty set of atomic meta-language expressions,
        2. Σm′ is a nonempty set of meta-language syntactic operators,
        3. S is a nonempty set of elementary meta-language function symbols,
        4. F is a possibly empty set of meta-language recursive function symbols over object language terms, and
        5. G is a possibly empty set of meta-language recursive function symbols over meta-language terms.

      Remark. 

      The canonical expressions of ML, Cm, close Am under Σm′, canonically express meanings, do not contain any μ operators or F/G functors, and rewrite derivations terminate with them.

      Remark. 

      The set S of the semantic vocabulary of Φ contains at least the semantic function symbol μ and is finite.

      Remark. 

      The set S(To) of μ-terms is the set of input terms to derivations, given by applying a semantic function symbol to an OL term.

      Remark. 

      F and G contain additional function symbols do not represent semantic functions, are not inputs to any rules in RΦ, but can take arguments from TO, S(To), and Cm.

      Remark. 

      The set Tm of meta-linguistic terms of ΣM is the closure of Am∪To under Σm′∪S∪F∪G.

      Definition. Complex indirect constant μ-systems (§ 8.3.4) [pagin2021-CIC]

      A complex indirect constant μ-system Φ must satisfy the following.

      1. RΦ is finite.
      2. For any rule, the rewrite variables on the rhs must be a subset of those on the left.
      3. Rewrite variables v1,v2,... take all and only object language grammatical terms as instances.
      4. Rewrite variables y1,y2,... take all and only expressions in Cm as instances.
      5. Every atomic rule r∈RΦ is of the form μi(t)→e where μi∈S, t∈AO and e is a simple or complex expression in Cm.
      6. For every pair ⟨μi∈S,t∈Ao⟩ there is an atomic rule.
      7. Every direct complex rule r has the form μi(α(v1,...,vn))→K(μk1(v1),...,μkn(vn))⇐Gr(α(v1,...,vn)) where Gr corresponds to grammaticality.
      8. Every indirect complex rule has the form μi(α(v1,...,vn))→f(μk1(v1),...,μkn(vn),v1,...,vn)⇐Gr(α(v1,...,vn)) where v1,...,vn are optional and f∈F.
      9. For every pair ⟨μi∈S,α∈Σo′, there is a unique complex (indirect or direct) rule.
      10. Every indirect ground rule is of the F-form f(y1,...,yn,...,tn)→K′(f′(y1,...,yn)) or the G-form g(e1,...,en)→K(e1,...,en) where f,f′∈F, g∈G, K,K′ are operators over Σm′, e1,...,en∈Am and t1,...,tj∈Ao, and at most one of the primed operators is null.
      11. Every indirect recurisve rule in RΦ has an F-form f(y1,...,yn,σ(v1,...,vn))→K(f(y1,...,yn,v1)...,f(y1,...,yn,vn)) or G-form g(K(y1,...,yn))→K′(g′(y1,...,yn)) where f∈F, g,g′∈G, K,K′ are operators over Σm′, σ∈ΣO′, and at most one of the primed operators is null.

      Proposition.  [pagin2021-cic-terminate]

      Complex indirect constant systems are convergent (§ 8.3.4).

      Corollary.  [pagin2021-mdl]

      Given a complex indirect constant μ-system, for any term t, there is some minimum derivation length to a unique normal form.

      Proposition.  [pagin2021-general]

      Let Φ be any complex indirect constant μ-system satisfying the following.

      1. For every n⩾1, there are object-language atoms a1,...an∈Ao such that for every 1⩽k⩽n, where t1=α1 and tk+1=δ(αk+1,tk), for some canonical expression e∈Cm, μ(tk)→Φ+e, and tk∈To.
      2. The complex rule for μ,δ is μ(δ(v1,v2))→f(μ(v1),μ(v2),v2)⇐Gr(d(v1,v2)).
      3. There are rules f(y1,y2,δ(v1,v2))→K(f(y1,y2,v1),f(y1,y2,v2)) and f(y1,y2,α)→Kα(y1,y2) for each α∈Ao.

      Then Φ is intractable.

      Lemma. 

      Fix some k⩾1 and α1,...,αk. Define F(t):=f(μ(αk+1,μ(tk),t′)).

      Moreover, define l(t) as the number of atomic leaves of t.

      For every object-language subterm t of tk, T(F(t))⩾l(t)·T(μ(tk)).

      Proof. 

      By structural induction on t.

      If t=α∈AO, F(α) has subterm μ(tk), which must be reduced to eliminate m to obtain a canonical form. Moreover, there is only one atomic leaf. So T(F(a))⩾T(μ(tk))=1·T(μ(tk)).

      Suppose t=δ(t1,t2). Normalisation requires elimination of the root f of F(t). Since the third argument has head δ, only f(y1,y2,δ(v1,v2))→K(f(y1,y2,v1),f(y1,y2,v2)) will do so. Every derivation (minimum-length or otherwise) will have to apply that rule at some point. Without loss of generality, apply it at the beginning. Then F(t)→K(F(t1),F(t2)). Note K is terminal by definition of complex indirect constant μ-systems. So T(F(t))=1+T(F(t1))+T(F(t2))⩾l(t1)·T(μ(tk))+l(t2)·T(μ(tk))=l(t)·T(μ(tk)).

      Proof.. 

      Now consider a minimum-length derivation of μ(tk+1). There is some minimum-length derivation that begins μ(tk+1)→F(tk) whence T(μ(tk+1))=1+T(F(tk))⩾k·T(μ(tk)) whence T(μ(tn))⩾(n−1)!.

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

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

      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.

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

      Distinction. 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 Θ(n2100) 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.

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

      Argument. The physicalist argument for asymptotic analysis of language

      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.

      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 x1,x2,x3,... (e.g. linguistic input). It may turn out that the probability distributions from which x1 and x2, for instance, are drawn are not independent. For simplicity, however we may assume that x1,... 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. 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.

      Definition. Turing machines (informal) [0019]

      • 27 April 2026

      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∈[0,1]∗. 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—

      Worries about Turing machines [001B]

      • 27 April 2026
      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.

      Definition. Polynomial time [001C]

      • 27 April 2026

      We say that the runtime of an algorithm is polynomial if its runtime is f(n)∈O(nk) for some fixed k.

      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.

      Note. Asymptotic analysis of algorithms [0018]

      • 27 April 2026

      We begin with a preliminary example.

      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.

      Operation. 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 ⟨a,b,c⟩. So if there are two comparison-cum-swaps, there are at most 2×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⟩.
      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.

      Problem. List-sorting

      Given a list of n numbers to sort, as a function of n, how many comparison-cum-swaps do we need?

      Similarly, other problems of arbitrary size can be posed.

      Problem. Travelling salesman

      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?

      Problem. 3-SAT

      Given a formula over n 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 nlogn (Hoare, Quicksort). The complexity of 3-SAT is open, but widely conjectured to be exponential.

      Question. What does ‘approximately’ mean here?

      Answer. 

      Asymptotic analysis makes this precise. Here we shall mostly follow Cormen, Leiserson and Rivest (Introduction: § 2.1).

      Definition. Tight bounds

      Given a monotonically non-decreasing function g:ℕ→ℕ, we write Θ(g(n))={f(n):there exist positive constants c1, c2, and n0 such that, for all n⩾n0, 0⩽c1g(n)⩽f(n)⩽c2g(n)}.

      Example. 2n∈Θ(n)

      Proof. 

      For all n⩾1, 0⩽12·2n⩽n⩽n⩽1·2n.

      Example. n3∉Θ(n2)

      Proof. 

      Suppose otherwise; then n3⩽c2n2 for all n⩾n0 as above, but this is contradictory if n>c2.

      Definition. Upper bounds

      Given a monotonically increasing function g:ℕ→ℕ, we write O(g(n))={f(n):there exist positive constants c and n0 such that, for all n⩾n0, 0⩽f(n)⩽cg(n)}.

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

      Proposition. Quicksort II

      The task of sorting a list of n numbers takes Θ(nlogn) comparison-cum-swaps.