Language Complexity (Part 1)

David A. Tanzer

A simple view of languages

How complex is the English language? The question has many dimensions and nuances. What does complexity mean, and how could it be measured? This a tough nut to crack, so in this post we’ll make a retrenchment to reconsider the question in a more formal setting — computer science.

In this setting, a language gets identified with its extension — the collection of all its sentences. So English gets modeled as just a large repository of sentenc...