On Mon, 2006-11-06 at 11:34 -0700, 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.
The mistake you are making is that although in theory an infinite string will require infinite time to process, we can prove inductively that it will in fact reach the end of the input, even if the end is infinity. This is different from the halting problem as the halting problem describes a set of problems where the input string may be fixed but the turing machine head is going back and forth (not quite the right words here) but we cannot prove whether it will ever reach the end of the string or just loop forever. Anyway these are two different sets of problems, one which is provable (the matched paren problem is probably solvable) and one which is not. Michael > > Dan > > On 11/6/06, Levi Pearson <[EMAIL PROTECTED]> wrote: > > 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 > > /* > PLUG: http://plug.org, #utah on irc.freenode.net > Unsubscribe: http://plug.org/mailman/options/plug > Don't fear the penguin. > */ > /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
