Emil Post

Not many people know who Emil Post was, but his model of computational processes as generating systems is one of the simplest to understand. It sits somewhere between the combinator calculus of Curry and Schönfinkel and Church's Lambda Calculus.

See Geoffrey K. Pullum's Creation myths of generative grammar and the mathematics of [Chomsky's] Syntactic Structures.

Post proved his Normal Form Theorem for Post canonical systems which shows that "Given any Post canonical system on an alphabet A, a Post canonical system in normal form can be constructed from it, possibly enlarging the alphabet, such that the set of words involving only letters of A that are generated by the normal-form system is exactly the set of words generated by the original system". What this shows is that a Post canonical system which generates a language can be abbreviated by adding non-terminal symbols which allow sub-structures to be reused at multiple places, thus potentially simplifying the grammar. 

I came here after hearing Bob Harper's remarks about Lambda Calculus being the only essentially linguistic model of computation in Bob Harper's Course on Principles of Programming Languages and then watching this video about Zipf's law:

Here's his video from three weeks ago:

... and the follow-up from a couple of weeks ago:

 

Subscribe to Edwin Wagha.

Probabilistic grammars were first studied in the 1950s by Solomonoff and others. See John A. Goldsmith's Probabilistic Models of Grammar: Phonology as Information Minimization where he says "My goal in this paper is to provide an introduction to the notion of a probabilistic grammar, and in particular, a probabilistic phonology. The notion of a probabilistic grammar is not a new one; it originated in the 1950s in work by Ray Solomonoff and others, and has played an increasingly important role in computational syntax and in speech recognition over the last fifteen years (Solomonoff 1997, Charniak 1993). The notion of a probabilistic grammar is, however, relatively unknown in mainstream linguistics, ..." 

Ray Solomonoff

Raymond Solomonoff died in December 2009. He was born on July 25, 1926 so his centenary will be in a few days.

Subscribe to Adrian German.

From the Wikipedia page on Zipf's Law: In 1957 George A. Miller proposed that a power law emerges even in randomly generated texts [see Some Effects of Intermittent Silence] and in 1992 bioinformatician Wentian Li published a proof that the power law form of Zipf's law was a by-product of ordering words by rank [see Random texts exhibit Zipf's-law-like word frequency distribution]. 

Here's an explanation of Benford's Law:

Subscribe to Khan Academy.

In that video they considered a few sequences like powers of two, Fibonacci sequences etc. Here's James Grime on Newton's method of finite differences:

... and a follow-up where he points out that it works for any sequence whatsoever, not just arithmetic, geometric, polynomial etc: 

The connection to the explanation of Benford's law (and possibly also Zipf's law) is because of the way every finite sequence can be described as a finite series of constant differences of differences of differences, ...  In the case of frequencies of words generated by a Post canonical system in a normal form with probability distributions generated by some underlying model, see Solomonoff's talk at 39:21 where he describes a similar problem and at 52:47 where he explicitly mentions grammar discovery as a technique. At 1:07:41 he expands on this idea a little.

Maybe there is some way to classify the kinds of distribution which give rise to Zipf's law to see whether there is something beyond just the word frequencies which identifies meaningful information. One would expect there to be something like a maximum entropy condition induced by the way language is used to communicate reliably. See The Unity of Nature, Least-Action, and Natural Social Science by George Kingsley Zipf (if you're the right kind of person, which I'm not):

 

See the Wikipedia pages for Probabilistic context-free grammar and Bayesian network. You can get an idea of he kind of analyses people do today from the thesis Extraction of Quantitative Grammatical Rules from Syntactic Treebanks by Santiago Herrera.

Subscribe to singingbanana.

This is also related to this post on Mach's The Economical Nature of Physical Enquiry. 

The greatest perfection of mental economy is attained in that science which has reached the highest formal development, and which is widely employed in physical inquiry, namely, in mathematics. Strange as it may sound, the power of mathematics rests upon its evasion of all unnecessary thought and on its wonderful saving of mental operations. Even those arrangement-signs which we call numbers are a system of marvellous simplicity and economy. When we employ the multiplication-table in multiplying numbers of several places, and so use the results of old operations of counting instead of performing the whole of each operation anew; when we consult our table of logarithms, replacing and saving thus new calculations by old ones already performed; when we employ determinants instead of always beginning afresh the solution of a system of equations; when we resolve new integral expressions into familiar old integrals; we see in this simply a feeble reflexion of the intellectual activity of a Lagrange or a Cauchy, who, with the keen discernment of a great military commander, substituted for new operations whole hosts of old ones. No one will dispute me when I say that the most elementary as well as the highest mathematics are economically-ordered experiences of counting, put in forms ready for use.

In algebra we perform, as far as possible, all numerical operations which are identical in form once for all, so that only a remnant of work is left for the individual case. The use of the signs of algebra and analysis, which are merely symbols of operations to be performed, is due to the observation that we can materially disburden the mind in this way and spare its powers for more important and more difficult duties, by imposing all mechanical operations upon the hand. One result of this method, which attests its economical character, is the construction of calculating machines. ... 

See John Norton on "Landauer's Principle" and this video Toby did about William James Sidis' book, written around 1918-1920: The Animate and the Inanimate. This was published 20 years before James Jeans' The Mysterious Universe which made popular the idea of of the second law and the heat death of the Universe. It was also 24 years before Erwin Schrödinger published What is Life?

Subscribe to Tibees.