mozy contest: problem 1 PHP solution

Michael L Torrie torriem at chem.byu.edu
Mon Nov 6 12:20:18 MST 2006


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




More information about the PLUG mailing list