Invisible wrote:
> - 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.

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

> Or whether a given variable will ever be read/written?

Put a halt statement everywhere you read or write that variable.

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

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