> 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
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
