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.
> 
> So no GOTO then?

Forward goto, sure. :-)

> Basically, anything where flow control is data-dependent?

No. Well, yes, in a sense. You're trying to simplify something that's 
already trivially simple, and in so doing just raising questions about what 
you mean by your version of the words.  "Indefinite loops are out." A loop 
you can't look at and tell at compile time the maximum number of times it'll 
loop is an indefinite loop. While loops are not indefinite loops if you can 
tell at compile time how often they'll loop: See Eiffel's loops, for example.

Recursion is OK as long as you have an upper bound on how often you recurse, 
somehow.

> Seems to me that almost anything remotely useful to know is undecidable. 

Only on unbounded computers.

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