|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |