>> OK, so let me get this straight:
>>
>> 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.
> 
> Almost. The "property" is a property of the language the program 
> accepts, not the program. Note that a "language" in this case isn't the 
> programming language, but the mapping from inputs to outputs. In other 
> words, a "property" is a relationship between input and output, not a 
> property of the text of the program.
> 
> A "property" of a program is the subset of all possible functions that 
> has that property.  The property "halts when given an empty string" is 
> defined as "the set of all programs that halt when given an empty 
> string." The property "outputs the word 'green' somewhere" means "the 
> set of all programs that output the word 'green' somewhere".
> 
> The theorem states that you can't tell what properties a function has. 
> In other words, if you look at a property as a collection of functions 
> that does *that*, then you can only tell if a function has it or not 
> only if that set is universal or empty.
> 
> Spend a couple minutes looking at the "formal statement".
> 
>> This seems downright false. For example, some programs contain a 
>> variable named "X", while others do not. 
> 
> That's not a property of the program. That's a property of the source 
> code used to describe the program. The exact same program may or may not 
> have an X. If you replace X with Y everywhere, the exact same program 
> (defined in terms of its inputs and outputs) doesn't have an X.

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?

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

Post a reply to this message