Invisible wrote:
>>> Now, if only it wasn't completely incomprehensible...
>>
>> What part do you not understand?
> 
> 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.

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message