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