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