5 ms·
The real insult is that the actual underlying idea, and the proof, is shockingly simple. It is essentially the pigeonhole principle: the principle that if you p
by xyzzyz 13y ago
The real insult is that the actual underlying idea, and the proof, is shockingly simple. It is essentially the pigeonhole principle: the principle that if you put more than n pigeons into n holes then there must be a hole with more than one pigeon in. Take the regular language L, and express it as a deterministic finite automaton with p states. Any string in L determines a path through the automaton; so any string with p or more characters must visit the same state twice, forming a loop. This looped part can be repeated any arbitrary number of times to produce other strings in L.
Yeah, that's how it is usually introduced to students. First you introduce them to finite state automatons, then you show them a cool trick of extending the words by walking in circles on the automaton's state graph, and only then you mention that this is basically a pumping lemma. After everyone understood the point of the pumping lemma, you write it down formally using five quantifiers, so that student can write it down concisely, as the idea is already understood at that point.
I agree that the formal statement of the pumping lemma can be very uninspiring, but it only hints to two important facts. First, it's very important to have a good teacher, who is able to introduce ideas in a way and order they work for you. Second is that in math, it's the proofs and ideas that are important, not theorem statements.
- sergiosgc 13y agoThis must beg the question: is math formal language expressive enough? Too often, the ideas are really simple but the mathematical formulation is extraordinarily complex. The first time I realized this was with Fourier transforms. Analytically, it is hell to understand the fundamentals, while if you read the original description by Fourier, it becomes dead obvious (as most great ideas, after the fact)
- abecedarius 13y agoHave a link to the original description? Apostol explained it with linear algebra, which made sense, but seems pretty magical in terms of how you'd notice sine waves make an orthogonal basis in the first place.
- contravert 13y agoI would like to see his original description as well. I've never understood the Fourier transform intuitively, no matter how much my professors and textbooks attempt to explain it. At this point, I'm just applying algorithms without fully understanding why I'm doing it.
- sergiosgc 13y agoIt was handed out as support material in a course. I can't for the life of me find it online. Anyhow, the transform hinges on two insights: you can use a point rotating in a circle as a basic building block and you can look at any signal as a sequence of spikes. This article looks like it follows the same approach: http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/ http://betterexplained.com/articles/an-interactive-guide-to-...
- xyzzyz 13y agoMath formal language is expressive enough to express everything most mathematicians want. The thing is that formal math language wasn't designed as a medium to transfer ideas, but rather as a notation to write them down concisely and make things easy to manipulate. That's why learning from books that are very formal is such a difficult experience, though it gets easier with experience. Unfortunately, to get to that level of experience, you pretty much have to be focused on pure mathematics for years, and if you're just trying to learn some math to get some other shit done, and there isn't any book written in more conversational style (which thankfully usually is the case), you're out of luck.