On 22-7-2009 18:24, Darren New wrote:
> 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. :-)

define forward
> 
>> 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.
> 
Perhaps also things that are decidable are not really useful to know. 
Example: you are going to die. See, not a bit of information added to 
the common knowledge, but is was decidable.

Post a reply to this message