Dynamical systems and formal languages

Faith in the connection between language and the dynamical unfolding of action in the world helps phoneticians to believe that Trubetzkoy was deeply mistaken when he wrote that "Phonetics is to phonology as numismatics is to economics".

But this faith can also be given some mathematical substance:

Cristopher Moore, "Dynamical recognizers: real time language recognition by analog computers", Theoretical Computer Science 201(1-2) 99-136 (1998). The abstract:

We consider a model of analog computation which can recognize various languages in real time. We encode an input word as a point in R^d by composing iterated maps, and then apply inequalities to the resulting point to test for membership in the language.

Each class of maps and inequalities, such as quadratic functions with rational coefficients, is capable of recognizing a particular class of languages. For instance, linear and quadratic maps can have both stack-like and queue-like memories. We use methods equivalent to the Vapnik-Chervonenkis dimension to separate some of our classes from each other: linear maps are less powerful than quadratic or piecewise-linear ones, polynomials are less powerful than elementary (trigonometric and exponential) maps, and deterministic polynomials of each degree are less powerful than their non-deterministic counterparts.

Comparing these dynamical classes with various discrete language classes helps illuminate how iterated maps can store and retrieve information in the continuum, the extent to which computation can be hidden in the encoding from symbol sequences into continuous spaces, and the relationship between analog and digital computation in general.

We relate this model to other models of analog computation; in particular, it can be seen as a real-time, constant-space, off-line version of Blum, Shub and Smale's real-valued machines.

[One weakness of this line of work is that it assumes infinite-precision numbers and no noise -- but the essentially ideas, at least those that are essential for current purposes, could be reconstructed in a more biologically realistic framework.]

OK, now back to bird brains.