On Nov 6, 2006, at 11:09 AM, Daniel C. wrote:
I may have the wrong word for it, but the language of matched
parentheses is not decideable with a Turing machine. That is, there
is no possible (real) Turing machine that can decide every string of
matched parentheses, because a string can be infinitely long and a
real Turing machine has finite storage space.
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.
*/
