mozy contest: problem 1 PHP solution

[Levi Pearson]

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