Welcome to the Signal Beat!

Here we cover a range of topics in math, programming, music and language. We hope you will find something interesting here to learn about!

See Units on the menu above, which is the key to what’s on the site. Each unit is a series of blog articles on a specific topic. So far we have two units on the math of epidemic models, and one on language complexity. Next on … Read more

Unit Overview – Language Complexity

David A. Tanzer, January 2021, in unit Language Complexity

How complex is the English language? That’s a tough nut to crack! Here we’ll reframe the question in a more formal setting which is shared by computer science and linguistics: the theory of formal languages and their complexity. By the end, we’ll reach a technical understanding of what is meant by the famous conjecture P != NP.

To talk about the … Read more

Language Complexity, Part 1

David A. Tanzer, January 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

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 and reconsider the question in a more formal setting — computer science.… Read more

Language Complexity, Part 2

David A. Tanzer, January 30, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Decision problems, decision procedures and complexity

In Part 1, we introduced the formal idea of a language, as being just a set of sentences. Now let’s approach the topic of language complexity.

For any given language, there is an associated decision problem:   given a candidate string of characters, determine whether or … Read more