mozy contest: problem 1 PHP solution

Levi Pearson levi at cold.org
Mon Nov 6 12:45:56 MST 2006


On Nov 6, 2006, at 12:20 PM, Michael L Torrie wrote:
>
> 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.

Actually, after re-reading things, I don't think that's what he was  
thinking of at all.  Let me take a crack at it, and we'll see if  
Daniel thinks I've characterized the article well.

When programming in C, C++, or Java (among others), standard numeric  
variables have a fixed size and roll over when they overflow.   
Therefore, an algorithm that relies on one of these variables to work  
will invariably fail when the capacity of that variable is exhausted  
and it rolls over.  So a naive algorithm that would work on a Turing  
machine breaks down in the real world not due to exhausting the  
memory on the machine, but simply exhausting the bits available in a  
variable.

This really has very little to do with Turing machines, and a lot to  
do with computer languages and their semantics.  The above languages  
are based on the semantics of the underlying computer (which, though  
capable of solving the same set of problems as a Turing machine given  
the proper programming and enough storage, are not the same) and so  
programs written naively in them have the same limitations of the  
underlying machine.

When matching of truly arbitrary strings is required, one can step up  
to using math libraries that support unbounded numbers for the  
parentheses count, and the problem goes away until the memory of the  
computer is completely exhausted, at which point you get a memory  
exhaustion error instead of an incorrect answer.

Or, one could use a language with different default semantics for  
numeric variables.  Common Lisp, for example, automatically promotes  
a fixed-size numeric variable to an arbitrary-size one when it  
overflows its bits.  This can cause an unexpected decrease in  
performance if you cause the promotion to happen with a big input  
string, but you never get a bogus answer due to variable overflow.

		--Levi



More information about the PLUG mailing list