mozy contest: problem 1 PHP solution

Justin Hileman justinhileman at
Sat Nov 11 16:57:29 MST 2006

> It was an interesting article, but the only thing I took away from it> is the idea that no real machine can decide all strings in the> language of matching parentheses because you can always exceed the> memory of the machine by one.the only problem is that matching parentheses can be decided by a linear bounded automaton (a special case of turing machine that doesn't have any more memory than its input string). so the only way to give it a string that it can't decide is to give it a string that it can't even accept as input.
Use Messenger to talk to your IM friends, even those on Yahoo!

More information about the PLUG mailing list