Why there must be universal grammar

The guardian ran an interview with Daniel Everett yesterday. Everett is a linguist most famous for his claim that universal grammar (the belief that some rules of grammar are "hard wired" into the brain) as popularized by Chomsky, is false. Specifically, he believes that the Pirahã language lacks recursion.

His claims are quite controversial, but one thing which is worth mentioning is that universal grammar is (for a reasonable definition of "proof") provably correct. By this I mean:

Theorem: Learning grammar is so hard that the only way humans (or anyone) can do it is if they have innate structures.

This is related to Chomsky's poverty of the stimulus argument.

It can be proven in the following way: suppose we restrict ourselves to just the subset of English sentences consisting only of nouns and verbs. "I like John" and "You are here" would be two examples. These both follow the pattern "noun verb noun". A sentence like "jump run you" is non-grammatical, because "verb verb noun" is not an acceptable pattern in English.

Now let's consider how long it would take a learner to learn these patterns. There are 2³ = 8 possible patterns of length three, so if a learner thinks they're all possible, it will have to test out all eight of them. ("Mommy, is 'jump run you' a sentence?")

Most sentences have much more than three words of course, so a learner will need to test out the 2⁴ = 16 four word patterns, the 2⁵ = 32 five word patterns, etc. In general, there are 2ⁿ possible sentences with n words, meaning that the number of tests that the learner will need to run is exponential in the number of words.

The Cobham-Edmonds thesis states that any problem which takes exponential time is, in practice, unsolvable.

Why is this true? There are, depending on your definition of "part of speech", about 20 parts of speech in English. If you tested one grammar per second, it would take you about a month to learn all the five word grammars. The six word grammars would take you two years, and you would be forty before you learned all the seven word grammars. That last sentence had 22 words, and it would take you 10²¹ years to test all of the 22-word-grammars. The universe is only 10¹³ years old.

So who knows whether all languages are recursive. But it seems unlikely that human children consider all possible grammars equally. They must use some shortcuts and those shortcuts must, by definition, be innate.

A Simple Proof: Occam's Razor

How do you know that I'm not a robot? How do you know we're not living in the matrix?

The usual resolution is some form of Occam's razor: sure, it's possible that I'm a robot, but the simpler explanation is that I'm human, and simpler explanations are preferable.¹

This just pushes the question back: why are simpler explanations better?

There is a straightforward proof that comes from Computer Science, of all places, which I hope to explain here.

---

Suppose I enter the world as a blank slate - I have a "bag" of hypotheses about how things work, and I consider them all equally probable. As I perform experiments, I disprove some of my hypotheses, while others remain. As time goes on, my bag of plausible hypotheses gets smaller and smaller.

If I eventually reach a point at which I only have two hypotheses remaining and I randomly choose one to believe, I'm 50% certain that I've got the right one. But if I randomly believe one out of a hundred possible hypotheses, I've almost certainly chosen wrong (i.e. I've probably selected a hypothesis that by luck happened to fit with all the observed data, even though it's in fact wrong).

Believe it or not, this concludes the proof.

If I have a simple hypothesis ("fire is hot") there's really only one other hypothesis that could be in my bag ("fire is not hot"), so I can rapidly determine which is the right one. If my hypothesis is complicated ("fire is hot, provided it's the first full moon of a year with zodiac symbol ...") there are tons of equally complex hypotheses, and some of them are bound to fit the data, so I'm unlikely to have chosen the right one.

---

In my job, I spend some time in the back rooms at medical offices, which means I hear nurses complain about doctors, and doctors complain about patients. One conversation I had with a dietition sticks into my memory: she was complaining about patients who expect the faddish, complicated dietary advice you hear on TV - "good" carbs, antioxidants etc. - but all she does is give people a calorie target, and recommend eating more fresh fruits and vegetables.

I told her to give her patients a brochure on Occam's razor. I doubt they've implemented my suggestion.

Postscript: This proof is a vague mishmash of the motivation for Bonferroni correction and VC theory. Any book on computational learning theory will have a better one, but you can see de Wolf's thesis for an explicit application of PAC learning to Occam's razor. You might also like my post why you will never see an eight-sided snowflake.

1. That's not true. The usual resolution is to ignore the problem.

Why I'm not super-enthusiastic about humane meat

The argument from marginal cases asks us to consider a child with a severe mental handicap. They are able to do simple physical tasks like feed themselves and move around, but unable to communicate beyond basic grunts.

What, the argument asks, is the difference between this child and, say, a cow? There are of course many superficial distinctions, but it's hard to find some difference which could plausibly be considered relevant. And of course if some distinction were found (maybe our hypothetical child has a stronger sense of self), we can simply change our theoretical mental handicap appropriately.

Peter Singer made this argument famous, and in On Being Silenced In Germany he talks about how it makes him uniquely vulnerable to misquotation. He'll have some line like "so we should consider severely mentally handicapped people roughly morally equivalent to pigs" and his opponents will gleefully describe how Prof. Singer wants to raise mentally handicapped children in factory farms and torture them to death so we can eat their sweet, sweet flesh.¹

Of course even a quick glance at Singer's Wikipedia page will make it obvious that he means the reverse: we should treat pigs with much more respect than we currently do. But it's at least a philosophically interesting question: why shouldn't we be free to kill mentally handicapped people?

---

While reading Nicollette Niman's article claiming that "humane" meat is ethical and the associated responses the article generated, it seems like the argument from marginal cases - which acted like a bombshell in my life - has had little impact on most people.

Most of the article is unremarkable; it solidly hits the three N's of meat eating (it's natural, necessary, and normal), but I suspect that a more careful reworking of her essay could remove some of the more ridiculous claims while still keeping the core message: "it is ethically defensible [to eat meat] -- provided we refrain from causing gratuitous suffering."

Maybe there isn't anything wrong with killing animals for food. Given that we're killing tens of billions of them per year, I desperately hope there's nothing wrong with it. But then why would there be anything wrong with killing the mentally disabled?

1. Apparently A Modest Proposal is not required reading in German schools.

A Simple Proof: Why you will never see an eight sided snowflake

Suppose you take a bunch of equally-sized marbles and squish them from all sides. You'll get one of two shapes:

These configurations are referred to as "rectangular" and "hexagonal":

Certain crystals have a molecular structure similar to these patterns, which is reflected in their macroscopic structure:

Halite, a rectangular crystal, and quartz, a hexagonal crystal.

A theorem known as the crystallography restriction states that hexagonal symmetry is the most that any crystal can hope to have - you will never see an eight-sided snowflake.

Formalizing a crystal

This theorem involves only basic trigonometry, but it does require us to most formally state what we mean by a "crystal". (If you know some basic linear algebra, most of this won't be a surprise to you.) The concept we're looking for is a discrete lattice, which has two relevant properties:

1. Every two points are some finite distance apart (i.e. points aren't infinitely close together).
2. The structure repeats along some line, meaning that you can slide the entire thing some finite distance along that line and get back what you started with. Another way of describing this is like an abstract version of addition. Basically, draw two lines which both start and end in the center of some circles. When you place the lines end to end, the last one will still be in the center of some circle. (So "adding" two lines together gets a valid third line.)

The blue line and the red line can be "added" together to create the valid green line.

Lastly, we need some way of describing what exactly we mean by having a "six-sided" crystal. Just like we can describe "sliding" repetition with addition of lines, we can describe rotational symmetry with rotations of lines.

The blue line can be rotated to create the valid green line.

Down to earth

As a warm up to our theorem that 6 is the most sides that a crystal can have, let's prove that no crystal has 5 sides.

Suppose we have something with five sides (i.e. a pentagon). If it were a lattice, we could add any two lines together to get a third line. So let's bring the yellow line down as the red one, and add it to the blue one. But this doesn't terminate on a point. So we can't add any two lines together, meaning it can't be a lattice. QED.

The general case is only somewhat more complex. Start with the yellow line, then rotate it by some angle θ to get the blue line. Subtract the yellow line from the blue line to get the green line. If θ is less than 360/6, the green line will be shorter than the yellow line.

We stated in our definition of "discrete lattice" above that every two points must be some finite distance D apart from each other. Phrased differently, every line must have a length of at least D. But we showed above that, if a rotation by θ is legal, we can get smaller and smaller lines - eventually we will get one smaller than D, causing a contradiction.

Therefore, any lattice must not have a rotation smaller than 60 degrees. QED.

So if anyone tries shows you an octagonal snowflake this holiday season, either they're lying, or they violated the laws of math to make an xmas miracle.

Appendix

I didn't really prove that the green line would be smaller. It's not too long, but it's not terribly interesting, so I'll just leave a link to wikipedia.

Update: I was worried that this would make the post too long, but here's a proof that the green line will be shorter. Starting from O, draw some line out to A. We only care about if the line gets shorter, not its absolute length, so let's just assume that the line $\overline{OA}$ has length one. Rotate $\overline{OA}$ to find point $B$, and subtract $\overline{OB}-\overline{OA}$ to get $C$. Since $\overline{BC}$ and $\overline{OA}$ are parallel, the angles $\angle AOB$ and $\angle OBC$ are equal. By the law of cosines, $\overline{OC}$ has length $\overline{OB}^2 + \overline{BC}^2 - 2 \overline{OB}\cdot\overline{BC}\cdot\cos\theta$. Recalling that $\overline{OA}=\overline{OB}=\overline{BC}=1$, we get that $\overline{OC}=2-2\cos\theta$. If $\theta\lt 60^{\circ}$, then this value will be less than one, meaning that $\overline{OC}\lt\overline{OA}$. So $\theta\geq 60^{\circ}$. QED.

The ugly pictures were created by me. The good-looking pictures courtesy of Wikimedia.

You might also like

• Angle trisection for dummies
• Using modular arithmetic to improve card games
• Undecidability for dummies
• Divisible by three

Using Modular Arithmetic to Improve Card Games

There was recently a discussion on patterns in modular arithmetic, in which the author showed some interesting pictures that result from plotting various functions. They introduced modular arithmetic by the standard appeal to time (an example wikipedia follows too) including the awesome fact that Japan uses neither a 12 nor a 24-hour clock - they will talk about things occurring at 28 o'clock (four AM tomorrow).

I get tired of hearing the same examples as common applications of modular arithmetic, so here's my contribution.

The basic point is that, for some applications, discreteness matters. If you want to divide up $5 among 3 people, and you are writing checks, you can just give each of them a fractional dollar amount. Problems only occur if you have 5 $1 bills and you can't make change.

A common example of this is card games - you frequently want to deal an equal number of cards to everyone and you can't exactly rip a card in half to make it work. Our standard deck has an abysmal 52 = 2*2*13 cards, which means that it's evenly divisible among 2, 4 or 13 players, resulting in our inability to play Hearts with 3 or 5 players.

What you really want is a number with a lot of prime factors, an idea roughly captured by the number's abundance. If our deck had 60 = 2*2*3*5 cards, we could play hearts with two, three, four, five or six players.

---

This idea occurred to me while playing Clue (apparently known as "Cluedo" outside the US). The game involves taking three cards out of the deck and then dividing the rest among the players. It supports 3-6 players, so finding the optimal number of cards involves finding a number that:

1. Has a remainder of three when divided by 3
2. Has a remainder of three when divided by 4
3. Has a remainder of three when divided by 5
4. And has a remainder of three when divided by 6

The solution to this problem can be found using the Chinese remainder theorem which, like all theorems discovered by people with foreign-sounding names, is titled after the discoverer's country (cf. Polish notation). It turns out that the first two solutions are 3 and 63 cards, which would make for either a really short or a really long game of Clue[do].

According to Wikipedia, the original design of the game called for 29 cards which leaves 26 after removing the three to hide in the envelope. The astute reader will see that 26 = 13 * 2, meaning the game could only work correctly if there were two or thirteen players!

Parker Brothers revamped the game to have 21 cards total, leaving 18 to divide among the players. This works out perfectly for three and six players, but leaves a couple extra cards when four or five people play. An improvement to be sure, but better options include 15 and 27 cards, both of which fail to divide in only one case.

---

Anyway, these are a couple examples of why we you might find the integers interesting. Of course there are many more (virtually every form of modern cryptography springs to mind) but hopefully these are some easy to understand instances.

Angle trisection for dummies

Continuing my line of posts explaining complex proofs by skipping the hard part, this post gives a proof that certain angles cannot be trisected. Terry Tau recently had a post on the same subject, which contained a very long proof using only basic geometry and a very short proof using Galois theory. The proof I use here is between the two he presents in both difficulty and length. It's a remarkable proof in that there's very little geometry per se, most of the proof would usually be classified as algebra.

As a crash course on what we mean to say an angle can be trisected: We start by assuming you have a line of length one, a ruler and a compass. A number $n$ is "constructible" if, starting with these things, you can construct a line of length $n$. It's simple to see that if $a$ and $b$ are constructible, then $a+b$ is as well (just stick the two lines together). This means we can repeatedly add 1 to itself to generate all the natural numbers.

It's also possible to construct $ab$ and $a/b$, although this piece is harder to show. To start things off on the trisection proof, let's place a limit on what numbers can be constructed:

Lemma 1: All constructible numbers are the solution to either a linear or quadratic equation with constructible coefficients

To construct some points we can either:

1. Draw two lines and find their intersection
2. Draw a line and a circle, and find their intersection
3. Draw two circles, and find their intersection

The intersection will always be a solution to an equation of degree at most two. For example, if we have the lines $y=m_1 x + b_1$ and $y = m_2 x + b_2$ their intersection has x coordinate $m_1 x + b_1= m_2 x + b_2$ or $(m_1 - m_2) x + (b_1 - b_2)=0$, so $x$ is the solution to a linear equation with both coefficients constructible.

In cases 2 and 3, the x and y coordinates will be solutions to quadratics.

Lemma 2: The only constructible points are solutions to equations of degree $2^n$ for some integer $n$

For example, we could find the point which satisfies $x^2-2=0$ which is $x=\sqrt{2}$. Now that we can construct $\sqrt{2}$, so we can use it in our equation; for example we can find $x=\sqrt[4]{2}$ by solving $x^2-\sqrt{2}=0$.

We can repeat this process to find the eigth root, sixteenth root etc. but we can only find roots that are powers of two. More generally, we can only construct equations of degree two; their coefficients might themselves be solutions to quadratics so we have an equation of degree 4 over our original set, but we can never create an equation of degree 3 or 5 or 379.

Lemma 3: If an angle $\theta$ is constructible, then $\cos\theta$ is constructible.

$\cos\theta$ represents the adjacent side of a right triangle with hypotenuse 1 and adjacent angle $\theta$; since we can draw a line of length 1 we can use that as a hypotenuse, and if we could draw the angle $\theta$ we can construct the entire triangle.

Proposition: $\cos 20^\circ$ is not constructible

Once we've proven this, we'll have proven that $20^\circ$ is not constructible, and so an angle of $60^\circ$ cannot be trisected.

I'm sure you all remember the triple angle formula $\cos 3\theta = 4 \cos ^3\theta-3\cos\theta$, plugging in $\cos 60=1/2$ and rearranging we get that $4\cos ^3\theta - 3\cos\theta - 1/2 = 0$; to make it more obvious I'll substitute $x$ for $\cos\theta$: $4x^3 - 3x - 1/2 = 0$. So $x$ is the solution to this cubic equation, but Lemma 1 told us that constructible points are only solutions to equations of degree $2^n$. So $x$ is not constructible. QED.

Undecidability for dummies

It's been my experience that many important "complex" theorems are complicated in only one or two parts. Oftentimes, if you're willing to accept a lemma or two without proof, you can understand the entire thing. So this is a post explaining what I think is a fairly complicated topic, but there is a piece I don't try to prove. I hope the result is something that's understandable to anyone with a little programming experience.

One of the things which fascinates me most are "incompleteness" theorems. I understand how we can look at some individual solution and determine that it doesn't solve some problem, but the proof that no solutions exist seems a lot harder.

A foundational result in theoretical computer science is the undecidability of the halting problem. This states that, given some program P, there is no general way to tell if P will run forever or if it will eventually stop. For example, the following program:

for each integer x:
	if x + 1 = x, then halt
	else go on to the next integer

will run forever, because there's not integer which is the same as itself with one added to it. This program:

for each integer x:
	if x + 0 = x, then halt
	else go on to the next integer

will halt immediately.

So how can we prove that there is no general method to tell whether a program will halt? It's a proof by contradiction: suppose we have some method, let's say M, of telling if a program will halt. Consider the following program:

if M says *this program* will halt, then run forever
else if M says this program will run forever, then halt

For any method M, it will fail to correctly predict the behavior of our program. So for any method M, there must be at least one program whose behavior it fails to predict, which proves our theorem.

---

When I first learned this, I felt (and to a certain extent still feel) that it was kind of a cheap trick. In retrospect, I think this was due to the program's ability to refer to itself. This is the complexity that I left out of the post, but the basic idea isn't that hard: we can assign a natural number to every program (i.e. there's a "first" program, a second program, ...). Once we've done that, a program "referring to itself" can be accomplished via these numbers, e.g. program 12345 referring to program 12345.

One simple yet important extension to the halting problem is Rice's Theorem, which basically says that you can never prove anything about a program. Want to prove that your program won't crash? Tough. Someone asks you to prove your algorithm always gives the right answer? No can do.

If you're interested, you can see a list of undecidable problems, the most famous of which is Hilbert's tenth.