TTL computing

From: Thilo Schmidt <>
Date: Sat Apr 13 09:44:48 2002

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)


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

This archive was generated by hypermail 2.3.0 : Fri Oct 10 2014 - 23:34:30 BST