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.



A/Prof Russell Standish                  Phone 0425 253119 (mobile)
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 

Reply via email to