>> OK, so Rice's theorum applies only to the input/output behaviour of 
>> the program then?
>>
>> Does that mean it *doesn't* apply to things like time or space usage?
> 
> Correct.  If you have any (computable) bound on the time or space usage, 
> then it's easy to determine if a given program will exceed those bounds 
> in computing a function by simply running it and checking (note in the 
> space usage case you might have to run it exponentially longer than the 
> space bound).  If the program runs too long or uses too much space, you 
> can just terminate it and halt, so this property is decidable.

Right. So if I write a pure function (i.e., some code that takes some 
input and returns some output but does nothing else - aside from maybe 
allocating memory), it is impossible to tell anything about this 
function other than how long it's going to take and how much memory it's 
going to eat?

Hmm, well that's a fairly dissapointing result. Apparently static 
analysis is an entirely hopeless endevour...

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

Post a reply to this message