mozy contest: problem 1 PHP solution

Justin Hileman justinhileman at hotmail.com
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!
http://ideas.live.com/programpage.aspx?versionId=7adb59de-a857-45ba-81cc-685ee3e858fe


More information about the PLUG mailing list