mozy contest: problem 1 PHP solution
dcrookston at gmail.com
Mon Nov 6 11:34:44 MST 2006
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.
On 11/6/06, Levi Pearson <levi at cold.org> 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.
More information about the PLUG