On 11/6/06, Levi Pearson <[EMAIL PROTECTED]> 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 /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
