>> - 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