mozy contest: problem 1 PHP solution

[Levi Pearson]

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

> That characterizes part of what the article was about, but not all of
> it.  I've been looking but I'm not sure I'm going to be able to find
> it.  I seem to recall something about quantum computing being
> involved, and the question of whether the universe is finite or not.
>
> Just checked my saved sites on Reddit, which doesn't have it.  This
> makes the probability of my finding it extremely low, I'm afraid.

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.

Clearly we cannot compute everything that is theoretically computable  
by a Turing machine due to the finite nature of the universe (if it  
is indeed infinite, at least our lifespans and the resources we can  
directly harness are currently finite), but we have a whole branch of  
computer science dedicated to classifying just how difficult specific  
Turing-computable problems are to compute in the real world.  And  
certainly nothing we know how to build now can compute anything that  
can't be theoretically computed by a Turing machine.

Another possible misconception from your original statement:  Turing- 
completeness is not a property of a problem, but a language and/or  
machine.  A problem is not 'turing-incomplete', it is 'undecidable by  
a Turing machine'.  You used the latter terminology as well, but the  
former is technically incorrect, so I fear you may have conflated the  
two ideas.  A program may solve a problem in the theoretical realm of  
Turing machines, but be too inefficient to solve it on a real machine  
due to the fact that real machines are finite.  It may not even be  
possible to make a program that solves it on a real machine in the  
currently predicted remaining lifespan of the universe.  This does  
not mean that the problem is undecidable in the Turing machine sense,  
though.

		--Levi