|
![](/i/fill.gif) |
>> - What is the "most powerful" language for which you *can* tell is an
>> arbitrary program will halt?
>
> I forget what it's called, but basically anything with for loops instead
> of while loops does the trick. You have to rule out recursion also.
> Essentially, anything with indefinite loops is out, as far as I understand.
So no GOTO then?
Basically, anything where flow control is data-dependent?
>> Can you determine whether a particular execution path is ever taken?
>
> No. That's called the "printing problem". Put a halt statement on that
> execution path.
I had a feeling it might be undecidable...
>> Or whether a given variable will ever be read/written?
>
> Put a halt statement everywhere you read or write that variable.
This too.
>> You can't determine whether two programs do the same thing, but can
>> you determine whether one algorithm is the inverse of another?
>
> No, because then you could determine whether a third program does the
> same thing as the first, if they're both inverses of the same program.
>
> See how it goes?
Seems to me that almost anything remotely useful to know is undecidable.
How helpful...
Post a reply to this message
|
![](/i/fill.gif) |