mozy contest: problem 1 PHP solution

Daniel C. dcrookston at gmail.com
Mon Nov 6 13:57:43 MST 2006


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.

> 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.

It's too bad that my mind works the way it does because I recall
reading something about hypercomputers as well and now I think the
same article dealt with both but I don't think it did.  I need some
way to index the things I've read in the past so I can look them up
again in the future.

> 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'.

I am familiar with the difference between Turing completeness and
Turing decidability, but I can never keep the two terms pointing to
the right idea.  If anyone has a mnemonic they use, I'd appreciate if
you'd share it.

Dan



More information about the PLUG mailing list