Re: Penrose and algorithms

From: Russell Standish <lists.domain.name.hidden>
Date: Thu, 21 Jun 2007 23:11:51 +1000

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         	         hpcoder.domain.name.hidden
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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

Received on Thu Jun 21 2007 - 20:05:29 PDT