Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What is the enlightenment I'm supposed to attain after studying finite automata?

cstheory.stackexchange.com

Post reply on HN
Print view View original

11–20 of 66 posts

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#11

Post by plinkplonk »

jacquesm wrote: post #7
chimeracoder wrote: post #5

I was dreading taking Computer Science Theory for my undergraduate degree. Turing machines bored me when I studied them in my introductory class, and I saw the class as a necessary evil - a core requirement as well as a prerequisite for my compilers class. Boy, was I wrong. Despite what I'd anticipated, that class ended up being the single most useful CS class that I took. I had the fortune of taking the class with A…

Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is…

"Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats."

If you don't mind being taught by Prof Ullman instead, Coursera has a course on Automata coming up https://www.coursera.org/course/automata

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#12

Post by mcmatterson »

Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space, and the tape as moving through it. I always found that this lead to me thinking of the FA as a mechanical entity, driven by some sort of magical tape; a useful thought exercise to be sure, but not something that had many direct impacts on modern computing (outside of the obvious regular language avenues). If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register. It's a seemingly small difference of conception, but one that finally brought together two worlds for me that had evolved largely distinctly before then.

It's tough to give justice to this insight, except to say that it really helped crystalize the jump between the theoretical side of CS (which had always been clear to me, if never terribly 'real'), and the applied side of CS (which had always seemed to have evolved in some sort of semi-influenced paralel universe to theory).

I don't know that it's the enlightenment you're looking for, but it's the one that eventually found me.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#13

Post by charlieflowers »

jacquesm wrote: post #7
chimeracoder wrote: post #5

I was dreading taking Computer Science Theory for my undergraduate degree. Turing machines bored me when I studied them in my introductory class, and I saw the class as a necessary evil - a core requirement as well as a prerequisite for my compilers class. Boy, was I wrong. Despite what I'd anticipated, that class ended up being the single most useful CS class that I took. I had the fortune of taking the class with A…

Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is…

Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#14

Post by derleth »

ctdonath wrote: post #9

When you understand a subject well enough, the true basics become fascinating. Without the full round trip from introduction to complexity to revealed simplicity, the basics are nigh unto incomprehensible - yet giving new students an intro thereto at least shows them where they are going. Quantum mechanics is simple, but baffling to beginners; give them a taste and the "aha" moment will come in time. A = {0|1,...} A[…

> Quantum mechanics is simple, but baffling to beginners

Quantum mechanics is weird to us because we're human-sized and quantum effects are mostly gone at our scale. Therefore, the only language we have for actually doing quantum mechanics is mathematics, so it makes sense to get a firm grasp of the math first. Fortunately, the fundamentals of the math aren't that difficult. I like to think of quantum mechanics as being 'mind-bendingly simple' for that reason.

Scott Aaronson has a fascinating lecture on quantum mechanics seen as a branch of probability theory:

http://www.scottaaronson.com/democritus/lec9.html

> Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let's try to generalize it so that the numbers we used to call "probabilities" can be negative numbers.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#15

Post by eternalban »

mcmatterson wrote: post #12

Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space,…

> If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register.

It would seem an apt analogy for the (basic) Von Neumann architecture, but "modern" CPUs have a hierarchy of "cache lines" that quite neatly -- at least in my mind -- map to a FA "fixed in space" [the cache line], with a "magical tape" [virtual memory and cache coherence].

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#16

Post by andrewflnr »

jmduke wrote: post #4
javajosh wrote: post #3

It is to recognize the congnizing that you are doing about finite automata is itself composed of finite automata.

Not to be rude, but what do you mean by this?

(Your brain is a finite automaton) + (sliced "cognize" out of "recognize" to get a new word for thinking).

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#17

Post by mitchi »

btilly wrote: post #10

Apparently if you understand finite automata, you'll be more enlightened than Stack Overflow moderators. My bitter example for this is http://stackoverflow.com/questions/11314077/algorithm-for-ex... which question was deleted by moderators, then undeleted by HN members. See http://meta.stackoverflow.com/questions/138678/can-we-please... for the discussion on meta about the question, and http://news.ycombinator.com/it…

Yep, this is the stackoverflow I know. They have practically killed all the meaningful C++ activity on the website by closing duplicate questions. Maybe some easy questions have already been answered but they don't let junior members contribute by answering them. By the way Wikipedia is worse. In English anyway, in French it's cool.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#18

Post by cynicalkane »

derleth wrote: post #14
ctdonath wrote: post #9

When you understand a subject well enough, the true basics become fascinating. Without the full round trip from introduction to complexity to revealed simplicity, the basics are nigh unto incomprehensible - yet giving new students an intro thereto at least shows them where they are going. Quantum mechanics is simple, but baffling to beginners; give them a taste and the "aha" moment will come in time. A = {0|1,...} A[…

> Quantum mechanics is simple, but baffling to beginners Quantum mechanics is weird to us because we're human-sized and quantum effects are mostly gone at our scale. Therefore, the only language we have for actually doing quantum mechanics is mathematics, so it makes sense to get a firm grasp of the math first. Fortunately, the fundamentals of the math aren't that difficult. I like to think of quantum mechanics as be…

And imaginary numbers, and four-vectors, and spinors...

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#19

Post by javajosh »

jmduke wrote: post #4
javajosh wrote: post #3

It is to recognize the congnizing that you are doing about finite automata is itself composed of finite automata.

Not to be rude, but what do you mean by this?

Recursion is the key to enlightenment. There are may ways to achieve this recursion, and contemplation of finite automata is one of them. The point of recursion happens when you realize that the thought process which is considering finite automata is itself composed of finite automata. The subjective experience of recursion leads to enlightenment.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#20

Post by stuffihavemade »

martinced wrote: post #2

It's interesting that both the question and the answer do focus on pattern matching. I maybe mistaken on this but that is really just one use of FSMs. I've implement event-driven FSMs and to me the biggest "ah ah" moment was that it was trivial to make a list of valid (or non valid) state transitions. I used it in one particular case which was really complex (IMHO) to model and were my code was quickly becoming a gig…

You still create FSM's in functional languages though. Consider:

data Light = On | Off

toggle :: Light -> Light

toggle On = Off

toggle Off = On

So, the data structures represent the possible states, and the associated functions the transitions.

Post reply on HN