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

I believe it's called a "primitive recursive" language.

This is also relevant: 
http://en.wikipedia.org/wiki/Total_functional_programming

Post a reply to this message

Kevin Wampler wrote:
> I believe it's called a "primitive recursive" language.

Yes, that rings a bell. :-)

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

"Warp" <war### [at] tagpovrayorg> wrote in message
news:4a671eb6@news.povray.org...
> Invisible <voi### [at] devnull> wrote:

> > It's common knowledge that if you write an arbitrary program in a
> > Turing-complete programming language, it is impossible to determine
> > whether the program will ever halt.

>   That's not stated correctly. It's impossible to create an algorithm
which
> would tell for all possible programs whether they terminate or not.

Even so, one has to be careful, for it's possible to determine if any such
finite program will halt or not - just run the program until all possible
states would be exhausted.

Post a reply to this message

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

On 22-7-2009 20:30, somebody wrote:
> "Warp" <war### [at] tagpovrayorg> wrote in message
> news:4a671eb6@news.povray.org...
>> Invisible <voi### [at] devnull> wrote:
> 
>>> It's common knowledge that if you write an arbitrary program in a
>>> Turing-complete programming language, it is impossible to determine
>>> whether the program will ever halt.
> 
>>   That's not stated correctly. It's impossible to create an algorithm
> which
>> would tell for all possible programs whether they terminate or not.
> 
> Even so, one has to be careful, for it's possible to determine if any such
> finite program will halt or not - just run the program until all possible
> states would be exhausted.

Why would the number of states be finite and why do you assume determinism?

Post a reply to this message

Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:

>>> So no GOTO then?
>> 
>> Forward goto, sure. :-)
> 
> define forward

Higher adress than current one in sequential memory?

Post a reply to this message

On 22-7-2009 21:05, Florian Pesth wrote:
> Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:
> 
>>>> So no GOTO then?
>>> Forward goto, sure. :-)
>> define forward
> 
> Higher adress than current one in sequential memory?
> 
Physical memory or logical?

Post a reply to this message

somebody <x### [at] ycom> wrote:
> Even so, one has to be careful, for it's possible to determine if any such
> finite program will halt or not - just run the program until all possible
> states would be exhausted.

  A finite program might never exhaust all possible states with unbounded
memory.

-- 
                                                          - Warp

Post a reply to this message

Am Wed, 22 Jul 2009 21:15:13 +0200 schrieb andrel:

> On 22-7-2009 21:05, Florian Pesth wrote:
>> Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:
>> 
>>>>> So no GOTO then?
>>>> Forward goto, sure. :-)
>>> define forward
>> 
>> Higher adress than current one in sequential memory?
>> 
> Physical memory or logical?

Logical and assuming the program and the MMU doesn't do "nasty" stuff :).

Post a reply to this message

On 22-7-2009 21:27, Florian Pesth wrote:
> Am Wed, 22 Jul 2009 21:15:13 +0200 schrieb andrel:
> 
>> On 22-7-2009 21:05, Florian Pesth wrote:
>>> Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:
>>>
>>>>>> So no GOTO then?
>>>>> Forward goto, sure. :-)
>>>> define forward
>>> Higher adress than current one in sequential memory?
>>>
>> Physical memory or logical?
> 
> Logical and assuming the program and the MMU doesn't do "nasty" stuff :).

I think we can safely assume that the program is in one block, or are 
there systems where parts of programs van be in more than one segment? 
Also assume that you can not execute something in a data or stack segment.
We have nearly pinned it.
Now we only have to make sure a compiler leaves the order of the 
statements in place or it knows compile time where everything will end 
up. Shouldn't be too difficult.
Codebuster's verdict: possible.

Post a reply to this message