On Fri, 11 Jul 2008 21:12:29 +0100, Orchid XP v8 wrote:

>>> The question, surely, is what functions are *not* computable by a
>>> computer? ;-)
>> 
>> I would think any problem that was mathematically intractable. :-)
> 
> Well, if you don't know "how" to solve a problem then you can't write a
> program that does it. That's true enough. I'm not sure it makes it not a
> "computable function" though...

There's a difference, though, between knowing how to solve a problem and 
being able to show - mathematically - that the problem grows at an 
exponential rate as the size of the problem is increased in a linear 
fashion.

>> Or put another way, some computational problems where the growth
>> function is exponential.  Some of those problems are solved on a small
>> scale computationally (like the traveling salesman problem), but as the
>> scale of the problem grows, the complexity grows as well.
>> 
>> At least that's what I remember from my discrete maths class in the
>> early 90's. :-)
> 
> Nope. That's not "impossible" to compute, just really damned slow. ;-)

I don't think it's about a specific size for the problem, but rather the 
growth pattern as the size of the problem is increased.

Doing something like calculating aircraft separation is an example of 
such a problem - it's the calculation of the intersection of oblique 
spheroids (because the separation is IIRC 5,000 feet horizontally and 
3,000 feet vertically).  With 2 plans that's easy.  With 20 planes it 
takes more time to calculate the intersections to determine if an 
airspace violation has occurred.

With 200 planes, it takes even more time.  With 2,000 even moreso.

And at some point, of course, you have to start over because planes 
aren't stationary in space - they move.

> If we're talking about what a computer can *theoretically* calculate.
> It's just a matter of leaving the machine running for long enough.
> 
> But even given infinite time and memory, a computer *still* can't solve
> the Halting Problem though. Even theoretically. Don't ask me why...

But this is an aspect I hadn't considered.

Jim

Post a reply to this message