Invisible wrote:
>>> Now, if only it wasn't completely incomprehensible...
> If there exists a property that some programs have and some other 
> programs do not have, it is impossible to tell which programs have this 
> property.
> 
> This seems downright false. For example, some programs contain a 
> variable named "X", while others do not. Yet it is trivial to determine, 
> for any possible program, whether or not it contains such a variable. So 
> this cannot possibly be what Rice's theorum is saying.

As noted in the first sentence of the Wikipedia article:

"Rice's theorem states that, for any non-trivial property of partial 
functions, there is no general and effective method to decide whether an 
algorithm computes a partial function with that property."

Wheather or not a program contains a variable named "X" is not a 
property of the function which it's computing -- it's only a property of 
the program itself so Rice's theorem doesn't apply.  Also note that 
generally within this context the functions are assumed to be on the 
natural numbers.

Post a reply to this message