mozy contest: problem 1 PHP solution
levi at cold.org
Mon Nov 6 11:19:38 MST 2006
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.
More information about the PLUG