mozy contest: problem 1 PHP solution
Levi Pearson
levi at cold.org
Mon Nov 6 13:48:21 MST 2006
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
More information about the PLUG
mailing list