>> So, to summarise:
>>
>>   For any property that some functions have and some functions don't 
>> have, it is impossible to tell whether a given function has that 
>> property just by examining the computer program that implements the 
>> function.
>>
>> (Or rather, for one specific program it might be possible, but it's 
>> not possible for *every possible* program...)
>>
>> Is that about right?
> 
> Yes, that sounds right to within the limits of english prose vs 
> mathematics. :-) Pluralize "computer program" and you're a touch closer, 
> since there can be many programs that implement the same function, but 
> you can't tell what they are. ;-)
> 
> Basically, you can think of it as "you can turn any problem into the 
> halting problem."  Anything that some programs do and some don't, you 
> can turn into the halting problem.

I wonder how many of these properties are decidable for "real-world" 
programs... I mean, the halting problem talks about ANY POSSIBLE 
PROGRAM. You could write something really freakin' bizare, and there's 
no hope of an algorithm puzzling it out. But I wonder if there are any 
useful properties that are decidable (or typically decidable) for useful 
programs...

Post a reply to this message