|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |