News for hackers. Stuff that matters.
Re:What is the enlightenment I'm supposed to attain after st... by mcmatterson on Sunday December 23, 2012 @10:43PM (#4961763)
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 st... by dbaupp on Monday December 24, 2012 @02:23AM (#4962168)
It sounds a bit like you are talking about a Turing machine rather than a finite automaton (the latter is much weaker than the former in computational power).

(Not that it matters much, your point still stands.)

Re:What is the enlightenment I'm supposed to attain after st... by marcosdumay on Monday December 24, 2012 @10:46AM (#4963124)
They are equivalent. None of them is weaker. And, by the way, your PC (Von Neuman architecture) is an example of finite automatum.

I've seen the FA formalism used in computing theory a few times. Yet, I'm also missing whatever enlightment the author is looking for. But, if for no other reason, it's worth learning just because it's a very nice tool.

Re:What is the enlightenment I'm supposed to attain after st... by robrenaud on Monday December 24, 2012 @10:59AM (#4963167)
Read the theory again. Finite automata are quite weak.
Re:What is the enlightenment I'm supposed to attain after st... by aaronblohowiak on Monday December 24, 2012 @12:11PM (#4963412)
Where is the infinite tape? Finite automata are as capable, in the real world, as Turing-like machines, because it is impossible to fabricate a machine with infinite storage.
Re:What is the enlightenment I'm supposed to attain after st... by jacquesm on Monday December 24, 2012 @04:49PM (#4964223)
Turing machines have infinite storage by definition, no such machine has ever been built (we're using approximations), real world restrictions do not apply to imaginary constructs.

If a Turing machine were not defined that way then you'd have to set some upper limit to the size of the tape and that in turn would have odd implications for what would be considered 'computable'. By making the tape infinite by definition you get much more meaningful answers about what is in principle computable and what is not.

Re:What is the enlightenment I'm supposed to attain after st... by mturmon on Monday December 24, 2012 @09:33PM (#4964875)
Indeed, we have done everything we can to provide ways to keep the illusion of running on a Turing machine going -- I'm thinking about mmap(), swapping to disk, tape robots, and databases, among others.

Yes, Virginia, you can always obtain more memory.

Re:What is the enlightenment I'm supposed to attain after st... by ncallaway on Monday December 24, 2012 @01:07PM (#4963573)
robrenaud did not respond to the argument that the PC is a Finite Automata.

His only comment was that "Finite Automata are quite weak" (in the context of the _theoretical difference_ between Turing machines and FA). He's absolutely correct. FA can compute a strict subset of what Turing machines can compute.

Re:What is the enlightenment I'm supposed to attain after st... by upquark on Monday December 24, 2012 @12:12PM (#4963415)
This is factually incorrect.
Re:What is the enlightenment I'm supposed to attain after st... by eternalban on Sunday December 23, 2012 @11:04PM (#4961809)
> 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 st... by jacquesm on Monday December 24, 2012 @12:25AM (#4961976)
The key insight is that they're essentially the same thing.
Re:What is the enlightenment I'm supposed to attain after st... by mcmatterson on Monday December 24, 2012 @09:44AM (#4962923)
Of course -- the reality of even the simplest CPU is obviously much, much more complex than what I described above. The analogy is really only helpful as a bridge between the world of theory, and the CPU as it exists in the world.
Re:What is the enlightenment I'm supposed to attain after st... by mcmatterson on Monday December 24, 2012 @09:45AM (#4962934)
Also, I'm interested in what you mean by the correspondence with cache hierarchies. Could you elaborate?
Re:What is the enlightenment I'm supposed to attain after st... by ruchir on Tuesday December 25, 2012 @12:31AM (#4965181)
I think Turing's key insight was that a special FA with a tape mechanism could be devised that could imitate any other FA. The power of this FA in imitating other FAs is limited only by the length of the tape.

However the improvement of this construction over any specific FA is that you have a device that can run any FA. As the length of the tape increases you have a device that can imitate the any and all possible FAs.

The CPU is precisely this FA which can imitate any other FA. The tape is memory.

However it is important to note that, at the end of it, any specific program that is being run on finite memory is still an FA.