mozy contest: problem 1 PHP solution

[Daniel C.]

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.

Dan

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.
>
>                 --Levi