I do concede that it's not a theoretical limitation at all. I'll have
to find the thing I read (if I can) and link y'all to it when I get
home from work.
Dan
On 11/6/06, Levi Pearson <[EMAIL PROTECTED]> wrote:
There is no such thing as a 'real' Turing machine, because Turing
machines explicitly do have infinite tape. And pushdown automata
explicitly have unbounded stack space. Since a Turing machine can
match any language that a pushdown automata can, and the language of
nested parentheses is pretty much the canonical introduction to the
increase of power a pushdown automata gives you over a finite-state
one, I think you're going to have to concede this argument. Please
do a quick google search on the concepts before replying again.
It is true that a physical computer cannot match the parenthesis in a
string that exceeds its ability to store the number of unclosed
parentheses, but that is hardly a practical limitation, and it is not
a theoretical limitation at all.
--Levi
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
