On Fri, 11 Jul 2008 21:00:36 +0100, Orchid XP v8 wrote:

>>> always assumed that "computable function" just meant "function that
>>> can be computed by a computer".
>> 
>> Yes. But the question is, what functions *are* computable by a
>> computer? That's kind of the point.
> 
> The question, surely, is what functions are *not* computable by a
> computer? ;-)

I would think any problem that was mathematically intractable. :-)

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

Jim

Post a reply to this message