Note. Computation, cognition and language [001E]
Our earlier conclusions (A model of computation) might be summarised as making the following conjecture: physically plausible models of computation do not differ in the problems they can solve in polynomial time.
What has this to do with language? To a certain extent, the argument must be reconstructed, but its rough outlines are clear.
A first premiss is the so-called Cobham–Edmonds thesis.
The Cobham–Edmonds thesis is only meaningful relative to a model of computation. But, if the van Emde Boas invariance thesis is correct, any reasonable model of computation will yield the same class of feasibly computable functions.
I shall, at this point, make a
The Cobham–Edmonds thesis might seem to admit obvious counterexamples. For instance, an algorithm that takes time seems obviously infeasible. (For that runtime to be meaningful, it would have to be associated with some privileged subset of the ‘reasonable’ machine-class above; a good example is e.g. physically instantiated computers.) Less obviously, there is some reason to suspect that some problems that likely have no polynomial-time algorithm are feasible. In this case, we might nevertheless hold that, most of the time, the Cobham–Edmonds thesis is correct. For instance, there are surprisingly few ‘galactic’ algorithms, i.e. algorithms with polynomial asymptotic runtime that in practice are unusable; see e.g. Helfgott (Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)
), Helfgott (Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman, ...)
), and Lipton and Regan (David Johnson
). We can therefore provisionally take the Cobham–Edmonds thesis to be a (defeasible) heuristic in the sense above.
What has this to do with language or cognition? There are, broadly, I think, two sorts of argument that relate asymptotic analysis to language.
For the sake of argument, I will assume that these arguments are right, and that, therefore, ‘language computations’ are amenable to asymptotic analysis.
Is the application of asymptotic analysis to cognition and language an idealisation? First, I shall give an example of computational analysis that plausibly is not an idealisation.
Let us suppose, with Searle (Rediscovery: 200), that
[T]here [is] some description of the brain such that under that description you could do a computational simulation of the operations of the brain…given Church's thesis that anything that can be given a precise enough characterization as a set of steps can be simulated on a digital computer…in the same sense in which weather systems, the behavior of the New York stock market, or the pattern of airline flights over Latin American can.
Turing (Computability
: § 11) showed that no Turing machine decides the Entscheidungsproblem. If we follow Searle’s rendering of Church’s thesis, it follows that the brain does not solve the Entscheidungsproblem either. I suggest there is no obvious idealisation here. (Of course, the argument might be false; but on its intended reading, it should be read as approximately false in the way idealisations usually are.) In other words, a fairly natural computationalist view is that these results from computability theory apply straightforwardly to computation generally, and, therefore, to cognition—and so to language computations.
However, in a considerable number of the arguments to follow, some antecedent assumptions seem to be false, and, therefore, the arguments will have to be parsed as idealisations. To say that the antecedent assumptions are false is not to deny computationalism. Suppose we are given a learning task over some stream of data (e.g. linguistic input). It may turn out that the probability distributions from which and , for instance, are drawn are not independent. For simplicity, however we may assume that 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.