anything like C++ references?

Moshe Zadka m at
Mon Jul 14 21:24:01 CEST 2003

[Moshe Zadka]
> In computer science, the theoretical model one first learns is a turing
> machine. Turing machines have no variables or values, merely tapes.

[Andrew Dalke]
> Actually, we started off with state machine, then worked our way though
> DFA/NFA, PDA, etc., ending up with a TM.

Obviously, I meant "first turing-equivalent". Of course, whether this
is true also depends: in CS "Computability" this is true, but
in Math, we covered this in "Logic 2", and there we did, IIRC,
recursive functions and counting machines first. Counting machines
are mostly useful as something on the way to prove recursive functions
are turing complete.

> I remember being intrigued
> that the way we learned these was in opposite order to they way they
> were first researched.
> Can anyone suggest why?  My thought was that mathematicians
> like generalizing, so the most general models were pondered first.
> Only as people started to experiment with variations, and with actual
> computer hardware to back them up, did people start thinking about
> more limited cases.

Well, I think that it's natural to study DFAs first, as a turing
machine is a DFA with a tape, so it's useful to know *why* the
tape is needed. Also, DFAs are a good explanation of "what are
computers", as a computer is necessarily finite. 
Moshe Zadka --
Buffy: I don't like you hanging out with someone that... short.
Riley: Yeah, a lot of young people nowadays are experimenting with shortness.
Agile Programming Language --

More information about the Python-list mailing list