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