mozy contest: problem 1 PHP solution

Levi Pearson levi at cold.org
Mon Nov 6 11:53:38 MST 2006


On Nov 6, 2006, at 11:34 AM, Daniel C. wrote:

> 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.

Not only is it not a theoretical limitation, but it's not a practical  
one either.  You can, in theory, create a string of parentheses too  
big to match for any given computer's internal storage space.  Such  
strings are not at all likely to show up in the real world, though,  
and even if they did, it's possible to work around them by augmenting  
the computer with additional storage space.

In terms of computational complexity, matching strings of parentheses  
is extremely easy, but you were attempting to make it look like some  
unsolvable problem.  I would be interested in seeing whatever article  
prompted you to make your original assertion, because I can't  
currently see how the point you were trying to make is relevant at  
all, except perhaps to keep programmers honest with the fact that  
their computers aren't real Turing machines because they have non- 
infinite memories.

		--Levi



More information about the PLUG mailing list