On Thu, Jun 21, 2007 at 09:29:11AM -0700, Pete Carlton wrote: > > it is disconcerting that he does not even address the issue, and > often writes as if an algorithm could have only the powers it could > be proven mathematically to have in the worst case. > > >
I agree with Dennett here. Just because the travelling salesman problem is NP-hard (and presumably incapable of being solved by a polynomial time algorithm), doesn't mean there aren't algorithms capable of getting within a few percent of the optimum route in polynomial time. These algorithms do exist, I've worked with them. So just because something is uncomputable, doesn't mean there isn't an algorithm for computing an approximation to it. \Omega, is the archetypical noncomputational number, yet someone has computed the first 1000 bits of it (See Li and Vitanyi for the details). And \Omega is probably a far worse problem algorithmically speaking than intuiting mathematical truth. Cheers -- ---------------------------------------------------------------------------- A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australia http://www.hpcoders.com.au ---------------------------------------------------------------------------- --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---
