>> 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...

> 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. ;-)

To a mathematician, 10^1534 years is a finite amount of time. In 
practical terms it's a ridiculously long time - many times longer than 
the current age of the universe, and plenty long enough for any 
hypothetical computer to exhaust all the available energy in the 
universe without reaching the end - but still, technically, a finite 
run-time.

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...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message