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"
Received on Sat Apr 13 2002 - 09:44:48 BST