Language Evolution and Computation Bibliography

The purpose of language is to encode information, so that it can be communicated. Both the producer and the comprehender of a communication want the encoding to be simple. However, they have competing concerns as well. The producer desires conciseness and the comprehender desires fidelity. This paper argues that the Minimum Description Length Principle (MDL) captures these two pressures on language. A genetic algorithm is used to evolve languages, that take the form of finite-state transducers, using MDL as a fitness metric. The languages that emerge are shown to have the ability to generalize beyond their initial training scope, suggesting that when selecting to satisfy MDL one is implicitly selecting for compositional languages.