4 ms·
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' (o
by mcmatterson 14y ago
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.
- eternalban 14y ago> 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].
- jacquesm 14y agoThe key insight is that they're essentially the same thing.
- mcmatterson 14y agoOf 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.
- mcmatterson 14y agoAlso, I'm interested in what you mean by the correspondence with cache hierarchies. Could you elaborate?
- dbaupp 14y agoIt 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.)
- marcosdumay 14y agoThey 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.
- robrenaud 14y agoRead the theory again. Finite automata are quite weak.
- aaronblohowiak 14y agoWhere 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.
- ncallaway 14y agorobrenaud 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.
- jacquesm 14y agoTuring 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.
- ruchir 14y agoI 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.