mozy contest: problem 1 PHP solution

[Levi Pearson]

On Nov 6, 2006, at 1:57 PM, Daniel C. wrote:

> On 11/6/06, Levi Pearson <levi at cold.org> wrote:
>> Well, that's too bad.  Sounds like it could have been an interesting
>> article, though I think its relevance to the mozy.com contest is
>> pretty tenuous, and I'd still like to see how Turing machines fit
>> into it.  Given your description of it and what I know of computer
>> science, I can't imagine what sort of point it was trying to make
>> with them.
>
> It was an interesting article, but the only thing I took away from it
> is the idea that no real machine can decide all strings in the
> language of matching parentheses because you can always exceed the
> memory of the machine by one.

That's not really a very interesting point in itself, though, since  
it's equivalent to the intuitively true statement that you could  
count as fast as you could for your entire life and still not count  
all the counting numbers.  It shouldn't require a very deep or  
interesting article to make that point clear, though I suppose it's a  
good thing to point out to people who have not thought much about the  
limits of physical computers.  It's just the tip of the limitation  
iceberg, though.

Clearly our real, physical machines have memory limitations, and if a  
linear growth in space requirements is our only obstacle to solving a  
particular problem, we're in pretty good shape since memory  
capacities have been growing exponentially for a while.  It's when  
memory requirements grow exponentially as well that we have  
problems.  And still, none of this has anything to do with Turing  
machines. :)

		--Levi