On 12-Apr-2002 Tony Duell wrote:
[excursion to theoretical computer science]
Then there's the Turing machnie. Again an fsm with
infinite memory (the
'tape), but memory that can be sequenctially accessed one cell at a time.
I believe nobody has ever proposed a machine that's more powerful than
the turing machine. I also seem to remember that a PDA with _2_ separate
infinite stacks is proveably equivalent to a Turing machine.
Yes, because if you
put everything on the second stack what you took from
the first stack you can simulate a tape... :-)
OK, those of you who actually learnt some computer
science, please
correct the above...
Not necessary, AFAIK everything said above was correct.
To get the hierarchy ("<=>" means equivalent):
FSMs <=> regular languages <=> primitive recursive functions
PDAs <=> context free languages <=> partial recursive functions
Turing Machines <=> context sensitive languages <=> computable functions
But this is getting heavily OT, so everyone further interested should
read the book about automata theory by Hopcroft and Ullman.
(I hope I got the names right, I've got the book but can't find it right now)
bye
Thilo
--
I am professionally trained in computer science, which is to say
(in all seriousness) that I am extremely poorly educated.
-- Joseph Weizenbaum, "Computer Power and Human Reason"