Orchid XP v8 wrote:
> 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.

Post a reply to this message