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 23 = 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 24 = 16 four word patterns, the 25 = 32 five word patterns, etc. In general, there are 2n 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 1021 years to test all of the 22-word-grammars. The universe is only 1013 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.