Infinite Loop Detector

[Gremlin]

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a fallacy built
on the assumption of mythical infinite all powerfull machines. In
reality we deal with finite machines that are capable of two states in
a loop, they either terminate, or repeat themselves. In the mythical
halting problem scenario machines are saposed to have a third state
where they never repeat themselves... still they teach this problem
to kids in school as a kind of dogma so when they see the following
code it will often times be some what of a suprise. Here I submit to
you for review an example implimentation of an infinite loop that has
a infinite loop detector built into it. It can deffinitly be improved
to run on external programs and you could speed it up a bit by
asigning a new value to buf on an exponential basis. This has made my
life an awfully lot easyer, now when I try to brute force sollutions I
know when I have succeeded or when I have failed, and sometimes now
turn problems that could be solved otherwise into brute force
solutions because it requires less work on my part but just a bit more
waiting.

#include <iostream>
using namespace std;
int main(){
int test=0;
int buf=-1;
while(1){
if(test==buf)
infinite=true;
break;
if(test%2==0)
buf++;
test++;
if(test%10000000==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==true)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!"<<endl;
return 0;
}

[Johannes Bauer]

Hi "Gremlin",

#include <iostream>
using namespace std;
int main(){
int test=0;
int buf=-1; ^ bool infinite; while(1){
if(test==buf) ^ { infinite=true;
break; ^ } if(test%2==0)
buf++;
test++;
if(test%10000000==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==true)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!"<<endl;
return 0;
}

Still, I don't get it. Doesn't make sense to me. Not any. At all.

Greetings, Joe

[Gremlin]

#include <iostream>
using namespace std;
bool infinite=false;
int main(){
int test=0;
int buf=-1;
while(1){
if(test==buf){
infinite=true;
break;
}
if(test%2==0)
buf++;
test++;
if(test%10000000==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==true)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!"<<endl;
return 0;
}

that's because my code had a few buggs in it.
I forgot to declare bool infinite, and needed to add some brakets around
one if statement.

Johannes Bauer <df***********@gmx.de> wrote in news:oe45h1-
vp*****@laptophost.laptopdomain:

Hi "Gremlin",

#include <iostream>
using namespace std;
int main(){
int test=0;
int buf=-1;

^ bool infinite;

while(1){
if(test==buf)

^ {

infinite=true;
break;

^ }

if(test%2==0)
buf++;
test++;
if(test%10000000==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==true)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!"<<endl;
return 0;
}

Still, I don't get it. Doesn't make sense to me. Not any. At all.

Greetings, Joe

[Gremlin]

whoops, sorry
I forgot a few lines of code
it should look like:

#include <iostream>
using namespace std;
bool infinite=false;
int main(){
int test=0;
int buf=-1;
while(1){
if(test==buf){
infinite=true;
break;
}
if(test%2==0)
buf++;
test++;
if(test%10000000==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==true)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!"<<endl;
return 0;
}

[John Cochran]

In article <3c**************************@posting.google.com >,
Gremlin <Gr*****@hotmail.com> wrote:

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a fallacy built
on the assumption of mythical infinite all powerfull machines. In
reality we deal with finite machines that are capable of two states in
a loop, they either terminate, or repeat themselves. In the mythical
halting problem scenario machines are saposed to have a third state
where they never repeat themselves... still they teach this problem
to kids in school as a kind of dogma so when they see the following
code it will often times be some what of a suprise. Here I submit to
you for review an example implimentation of an infinite loop that has
a infinite loop detector built into it. It can deffinitly be improved
to run on external programs and you could speed it up a bit by
asigning a new value to buf on an exponential basis. This has made my
life an awfully lot easyer, now when I try to brute force sollutions I
know when I have succeeded or when I have failed, and sometimes now
turn problems that could be solved otherwise into brute force
solutions because it requires less work on my part but just a bit more
waiting.

#include <iostream>
using namespace std;
int main(){
int test=0;
int buf=-1;
while(1){
if(test==buf)
infinite=true;
break;
if(test%2==0)
buf++;
test++;
if(test%10000000==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==true)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!"<<endl;
return 0;
}

Rather silly code here. It looks like nothing more than a test that will
cause the loop to be called "infinite" after 2 * UINT_MAX interations of
the loop. Not a solution to the halting problem at all.

[red floyd]

Gremlin wrote:

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a fallacy built
on the assumption of mythical infinite all powerfull machines. In
reality we deal with finite machines that are capable of two states in
a loop, they either terminate, or repeat themselves. In the mythical
halting problem scenario machines are saposed to have a third state
where they never repeat themselves... still they teach this problem
to kids in school as a kind of dogma so when they see the following
code it will often times be some what of a suprise. Here I submit to
you for review an example implimentation of an infinite loop that has
a infinite loop detector built into it. It can deffinitly be improved
to run on external programs and you could speed it up a bit by
asigning a new value to buf on an exponential basis. This has made my
life an awfully lot easyer, now when I try to brute force sollutions I
know when I have succeeded or when I have failed, and sometimes now
turn problems that could be solved otherwise into brute force
solutions because it requires less work on my part but just a bit more
waiting.

[redacted]

Because you're misinterpreting. You're not detecting an infinite loop,
you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in an
infinite loop itself, but whether a different program/UTM/whatever,
given program P as input, can say "P halts".

[Gremlin]

Rather silly code here. It looks like nothing more than a test that will
cause the loop to be called "infinite" after 2 * UINT_MAX interations of
the loop. Not a solution to the halting problem at all.

That is exactly what it does, but have you seen the new code I posted? The
message you are responding to had a few buggs in it still... This will
work idea will work in other scenarios besides this particular loop. This
is because the halting problem has to do with infinite machines and we are
working on finite machines. I never said it was a solution to the halting
problem, only that the halting problem is irrelevant on a finite memory
machine! You post an infinite loop of any kind and I will post back the
same loop with this sort of infinite loop detector appended to it, and you
will see it can indeed detect the loop. In a finite machine loops either
terminate or repeat never cary on in new ways forever...

[Gremlin]

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy. com:

Because you're misinterpreting. You're not detecting an infinite loop,
you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in an
infinite loop itself, but whether a different program/UTM/whatever,
given program P as input, can say "P halts".

You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your loop.
Some problems may not theoretically run in infinite loops but would of
course on a computer, the halting problem deals with theoretical problems
not reality.

[Mike Wahler]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy. com:

Because you're misinterpreting. You're not detecting an infinite loop,
you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in an
infinite loop itself, but whether a different program/UTM/whatever,
given program P as input, can say "P halts".
You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your

loop. Some problems may not theoretically run in infinite loops but would of
course on a computer, the halting problem deals with theoretical problems
not reality.

A is A.
If A is changed, then it's no longer 'A'.

You're talking in circles.

-Mike

[Gremlin]

"Mike Wahler" <mk******@mkwahler.net> wrote in
news:5m******************@newsread2.news.pas.earth link.net:

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy. com:

> Because you're misinterpreting. You're not detecting an infinite
> loop, you're detecting recurrence of data.
>
> Also, the Halting Problem is not if a program can detect if it is
> in an infinite loop itself, but whether a different
> program/UTM/whatever, given program P as input, can say "P halts".
>
>

You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your

loop.

Some problems may not theoretically run in infinite loops but would
of course on a computer, the halting problem deals with theoretical
problems not reality.

A is A.
If A is changed, then it's no longer 'A'.

You're talking in circles.

-Mike

Why don't you publish the axiom of choice instead?
Besides your logic is misleading in the world of computer programming.
Take this code for example.

int main(){
return 0;
}

it is equivalent to....

int main(){
//this is a comment
return 0;
}

[Andrey Tarasevich]

Gremlin wrote:

Rather silly code here. It looks like nothing more than a test that will
cause the loop to be called "infinite" after 2 * UINT_MAX interations of
the loop. Not a solution to the halting problem at all.

That is exactly what it does, but have you seen the new code I posted? The
message you are responding to had a few buggs in it still... This will
work idea will work in other scenarios besides this particular loop.

What John said applies to the new (corrected) version of your code.
Ignoring the fact that program relies on certain assumptions about the
nature of undefined behavior that takes place when type 'int' overflows,
the program simply waits till variable 'test' overflows and then
catches-up with variable 'buf'. This will happen after about '2 *
(INT_MAX - INT_MIN)' iterations, at which point the program will stop
its iterations and say that the loop is infinite.

I don't see what all this has to do with detecting infinite cycles in
particular and, more importantly, halting problem in general. Are you
sure that this is the right code? It looks more like an experiment
designed to prove that Achiless will eventually catch-up with Turtle.

--
Best regards,
Andrey Tarasevich

[Mike Wahler]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

"Mike Wahler" <mk******@mkwahler.net> wrote in
news:5m******************@newsread2.news.pas.earth link.net:

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy. com:

> Because you're misinterpreting. You're not detecting an infinite
> loop, you're detecting recurrence of data.
>
> Also, the Halting Problem is not if a program can detect if it is
> in an infinite loop itself, but whether a different
> program/UTM/whatever, given program P as input, can say "P halts".
>
>

You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your loop.

Some problems may not theoretically run in infinite loops but would
of course on a computer, the halting problem deals with theoretical
problems not reality.

A is A.
If A is changed, then it's no longer 'A'.

You're talking in circles.

-Mike

Why don't you publish the axiom of choice instead?

Not interested.
Besides your logic is misleading in the world of computer programming.
Really? How so?
Take this code for example.

int main(){
return 0;
}

it is equivalent to....

int main(){
//this is a comment
return 0;
}

Yes it is. Comments do not become part of the executable.
-Mike

[John Cochran]

In article <Xn******************@216.168.3.44>,
Gremlin <Gr*****@hotmail.com> wrote:

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy .com:

Because you're misinterpreting. You're not detecting an infinite loop,
you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in an
infinite loop itself, but whether a different program/UTM/whatever,
given program P as input, can say "P halts".

You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your loop.
Some problems may not theoretically run in infinite loops but would of
course on a computer, the halting problem deals with theoretical problems
not reality.

And I'll post a loop that terminates after about 3 * UINT_MAX iterations
and your "infinite loop" detector will claim that my loop is infinite even
though the loop would have terminated if your "detector" wasn't in place.

[Gremlin]

jd*@smof.fiawol.org (John Cochran) wrote in
news:c1***********@smof.fiawol.org:

In article <Xn******************@216.168.3.44>,
Gremlin <Gr*****@hotmail.com> wrote:

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodig y.com:

Because you're misinterpreting. You're not detecting an infinite
loop, you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in
an infinite loop itself, but whether a different
program/UTM/whatever, given program P as input, can say "P halts".

You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your
loop. Some problems may not theoretically run in infinite loops but
would of course on a computer, the halting problem deals with
theoretical problems not reality.

And I'll post a loop that terminates after about 3 * UINT_MAX
iterations and your "infinite loop" detector will claim that my loop
is infinite even though the loop would have terminated if your
"detector" wasn't in place.

That depends on how the detector is created for your loop.
For example:

unsigned int a,b,c;
a=0;
b=0;
c=0;
while(a<=UINT_MAX && b<=UINT_MAX && C<=UINT_MAX){
if(a<UINT_MAX)
a++;
else if(b<UINT_MAX)
b++;
else if(c<UINT_MAX)
c++;
}

That loop goes on for 3 * UINT_MAX, if I am not mistaken...

you could modify it to detect if it is an infinite loop like so:

unsigned int a,b,c,x,y,z;
a=0;
b=0;
c=0;
x=1;
y=0;
z=-1;
int i=0;
while(a<=UINT_MAX && b<=UINT_MAX && c<=UINT_MAX){

if(i==3)
break;

if(a<UINT_MAX){
if(x==a)
i++;
else if(a%2==0)
x++;

a++;
}
else if(b<UINT_MAX){
if(y==b)
i++;
else if(b%2==0)
y++;

b++;
}
else if(c<UINT_MAX){
if(z==c)
i++;
else if(c%2==0)
z++;

c++;
}

}

if(i==3)
cout<<"Infinite loop..."<<endl;
else
cout<<"halted"<<endl;

I may not have written a working program but I can correct it if you see
any errors...
At any rate you do raise a good point, because if you make a loop that goes
on long enough it could take a few years to find out if it terminates...
still it is better than running your program for 20 years thinking it does
terminate when in fact it doesn't.

[Jonathan Turkanis]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:3c**************************@posting.google.c om...

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not.

Here is a program that can detect if it is in an infinte loop:

#include <iostream>

int main()
{
while (true)
std::cout << "I'm in an infinite loop\n";
return 17;
}

Jonathan

[Andrey Tarasevich]

Gremlin wrote:

...
At any rate you do raise a good point, because if you make a loop that goes
on long enough it could take a few years to find out if it terminates...
still it is better than running your program for 20 years thinking it does
terminate when in fact it doesn't.
...

All your code does is that it basically counts iterations till some N
and than says "Since this cycle made N iterations, it must be infinite".
This is utter nonsense and doesn't prove anything.

Let's take a program that iteratively calculates sequence of digits of
Pi and looks for some particular subsequence in that sequence (my
telephone number, for example, followed by my birthdate). Currently
there's no way to determine in advance whether this cycle is going to end.

--
Best regards,
Andrey Tarasevich

[Cy Edmunds]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:3c**************************@posting.google.c om...

If you are not familiar with the halting problem, I will not go into
it in detail [snip]

Well, if you need power for the computer you run your program on, I have a
really neat perpetual motion machine you can use.

--
Cy
http://home.rochester.rr.com/cyhome/

[Julie J.]

> Let's take a program that iteratively calculates sequence of digits of

Pi and looks for some particular subsequence in that sequence (my
telephone number, for example, followed by my birthdate). Currently
there's no way to determine in advance whether this cycle is going to end.
The cycle will either terminate or repeat, but it can not go on forever w/o
repeating.

Andrey Tarasevich wrote:
Gremlin wrote:

...
At any rate you do raise a good point, because if you make a loop that goes
on long enough it could take a few years to find out if it terminates...
still it is better than running your program for 20 years thinking it does
terminate when in fact it doesn't.
...

All your code does is that it basically counts iterations till some N
and than says "Since this cycle made N iterations, it must be infinite".
This is utter nonsense and doesn't prove anything.

Let's take a program that iteratively calculates sequence of digits of
Pi and looks for some particular subsequence in that sequence (my
telephone number, for example, followed by my birthdate). Currently
there's no way to determine in advance whether this cycle is going to end.

--
Best regards,
Andrey Tarasevich

[Julie J.]

Further, presuming that your algorithm doesn't repeat, then it *must* terminate
on a finite (real) machine.

"Julie J." wrote:

Let's take a program that iteratively calculates sequence of digits of
Pi and looks for some particular subsequence in that sequence (my
telephone number, for example, followed by my birthdate). Currently
there's no way to determine in advance whether this cycle is going to end.

The cycle will either terminate or repeat, but it can not go on forever w/o
repeating.

Andrey Tarasevich wrote:

Gremlin wrote:

...
At any rate you do raise a good point, because if you make a loop that goes
on long enough it could take a few years to find out if it terminates...
still it is better than running your program for 20 years thinking it does
terminate when in fact it doesn't.
...

All your code does is that it basically counts iterations till some N
and than says "Since this cycle made N iterations, it must be infinite".
This is utter nonsense and doesn't prove anything.

Let's take a program that iteratively calculates sequence of digits of
Pi and looks for some particular subsequence in that sequence (my
telephone number, for example, followed by my birthdate). Currently
there's no way to determine in advance whether this cycle is going to end.

--
Best regards,
Andrey Tarasevich

[Jonathan Turkanis]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:3c**************************@posting.google.c om...

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not.

This might be as good a place as any to mention my new language
construct. It helps to solve the problem that sometime I want to do
something but I don't know how. The answer is to have the compiler do
it for me. It uses syntax similar to try-catch blocks. Here is an
example.

void f(std::vector<string>& applicants)
{

please {

// Note: this is no pseudo-code: compiler
// understands English

sort vector lexicographically, disccarding those
which contain spelling errors or are obviously fake

} thanks_anyway {

std::cout << "Sorry, too hard\n";
exit(-1);

}
}

I'm currently working on a proposal to standardize this extension. To
make life easier for implementators, it will be considered acceptable
for implementations to transfer control automatically to the
thanks_anyway block provided the compiler 'tried really hard' to solve
the problem. (A previous version required the compiler to try 'really,
really hard'.)

What do you think?

If I combine this with your idea I'll be able to handle the case where
the compiler gets stuck in a loop trying to solve the problem, or gets
bored and starts watching a movie.

Jonathan

[Andre Kostur]

"Julie J." <unlisted@.> wrote in news:40403A72.F3E4EC31@.:

Further, presuming that your algorithm doesn't repeat, then it *must*
terminate on a finite (real) machine.

"Julie J." wrote:

> Let's take a program that iteratively calculates sequence of digits
> of Pi and looks for some particular subsequence in that sequence
> (my telephone number, for example, followed by my birthdate).
> Currently there's no way to determine in advance whether this cycle
> is going to end.

The cycle will either terminate or repeat, but it can not go on
forever w/o repeating.

Please don't top-post...

There's a couple of points that I think you're missing. The OP has
presented the hypothesis that given a loop, he can adjust the loop to
detect whether it is infinite or not. This particular reply presents a
loop that cannot be determined in advance as to how many iterations it is
going to need to succeed/fail. pi has this property where the decimal
portion is non-repeating.

[Andrey Tarasevich]

Julie J. wrote:

Let's take a program that iteratively calculates sequence of digits of
Pi and looks for some particular subsequence in that sequence (my
telephone number, for example, followed by my birthdate). Currently
there's no way to determine in advance whether this cycle is going to end.

The cycle will either terminate or repeat, but it can not go on forever w/o
repeating.

I don't understand what you are trying to say. What exactly "can not go
on forever w/o repeating"?

--
Best regards,
Andrey Tarasevich

[John Harrison]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:3c**************************@posting.google.c om...

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a fallacy built
on the assumption of mythical infinite all powerfull machines.
Its not a fallacy, its just depnds upon an assumption you don't like,
In
reality we deal with finite machines that are capable of two states in
a loop, they either terminate, or repeat themselves. In the mythical
halting problem scenario machines are saposed to have a third state
where they never repeat themselves...
Right, an infinite machine.
still they teach this problem
to kids in school as a kind of dogma so when they see the following
code it will often times be some what of a suprise.
Only if the student wasn't paying attention when the teacher said 'infinite
machine'.
Here I submit to
you for review an example implimentation of an infinite loop that has
a infinite loop detector built into it.

This is a simple algorithm, commonly used to detect circular lists (for
instance).

What is your point exactly?

john

[Johannes Bauer]

Gremlin wrote:

that's because my code had a few buggs in it.
I forgot to declare bool infinite, and needed to add some brakets around
one if statement.

Ehrm, no, it ain't. If you read my post, you'll see I fixed exactly
those things.

The whole problem is that your infinite loop detector does not detect
infinite loops, but detects finite loops with more than n iterations.
This is a bad appoach to the problem, as mentioned by dozens of people
in this very thread.

Greetings, Joe

[Nick Hounsome]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy. com:

Because you're misinterpreting. You're not detecting an infinite loop,
you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in an
infinite loop itself, but whether a different program/UTM/whatever,
given program P as input, can say "P halts".
You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your

loop. Some problems may not theoretically run in infinite loops but would of
course on a computer, the halting problem deals with theoretical problems
not reality.

A little knowledge is a dangerous thing.
The theorem DOES NOT state that for any given program it cannot be proved
whether or not it halts.
In essence what it says is that you cannot write a program that will take
ANY source code
as input and tell you whether or not it will halt.
Your program doesn't even take any input so it cannot be such a machine.
Your post is also way off topic - this reinforces the point that you don't
read stuff thoroughly enough.
Or are you just taking trying to wind the c++ newsgrouop up?

[anon luker]

This is the second cross-post from virtual adepts that I've seen this
week. Both illustrated the kind of naive enthusiasm that has made
computer science such a fun field. You never see a business student
throw money at a problem trying to solve it, but programmers are often
unable to see the parallel. I applaud your attempt to challenge
convention and assert that the hard-won knowledge you end up with will
be yours forever.

Andre Kostur <nn******@kostur.net> wrote in message news:<Xn*******************************@207.35.177 .135>...

"Julie J." <unlisted@.> wrote in news:40403A72.F3E4EC31@.:

Further, presuming that your algorithm doesn't repeat, then it *must*
terminate on a finite (real) machine.

"Julie J." wrote:

> Let's take a program that iteratively calculates sequence of digits
> of Pi and looks for some particular subsequence in that sequence
> (my telephone number, for example, followed by my birthdate).
> Currently there's no way to determine in advance whether this cycle
> is going to end.

The cycle will either terminate or repeat, but it can not go on
forever w/o repeating.

Please don't top-post...

[Claudio Puviani]

"Gremlin" <Gr*****@hotmail.com> wrote

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a fallacy built
on the assumption of mythical infinite all powerfull machines. In
reality we deal with finite machines that are capable of two states in
a loop, they either terminate, or repeat themselves. In the mythical
halting problem scenario machines are saposed to have a third state
where they never repeat themselves... still they teach this problem
to kids in school as a kind of dogma so when they see the following
code it will often times be some what of a suprise. Here I submit to
you for review an example implimentation of an infinite loop that has
a infinite loop detector built into it. It can deffinitly be improved
to run on external programs and you could speed it up a bit by
asigning a new value to buf on an exponential basis. This has made my
life an awfully lot easyer, now when I try to brute force sollutions I
know when I have succeeded or when I have failed, and sometimes now
turn problems that could be solved otherwise into brute force
solutions because it requires less work on my part but just a bit more
waiting.

[snip]

This illustrates the old adage: better to be silent and let people believe that
you're ignorant than to open your mouth and prove it.

Claudio Puviani

P.S.: Don't cross-post.

[Gremlin]

Johannes Bauer <df***********@gmx.de> wrote in
news:i1***********@laptophost.laptopdomain:

Gremlin wrote:

that's because my code had a few buggs in it.
I forgot to declare bool infinite, and needed to add some brakets
around one if statement.

Ehrm, no, it ain't. If you read my post, you'll see I fixed exactly
those things.

The whole problem is that your infinite loop detector does not detect
infinite loops, but detects finite loops with more than n iterations.
This is a bad appoach to the problem, as mentioned by dozens of people
in this very thread.

Greetings, Joe

The only time that my program will detect anything is in the case of the
loop being infinite. It doesn't detect n iterations it detects when one
counter moving twice as fast as another counter is equal to the other
counter. This occurance only occurs when the loop is infinite, and on a
finite machine that means that the loop repeats itself.

[nog]

In article <Xn******************@216.168.3.44>,
Gr*****@hotmail.com says...

The only time that my program will detect anything is in the case of the
loop being infinite. It doesn't detect n iterations it detects when one
counter moving twice as fast as another counter is equal to the other
counter. This occurance only occurs when the loop is infinite, and on a
finite machine that means that the loop repeats itself.

PMFJI but I don't follow your reasoning - how does that
happen only when the loop is infinite? Surely it can happen
in a situation of n iterations if the value n is high
enough?

[Artie Gold]

Cy Edmunds wrote:

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:3c**************************@posting.google.c om...

If you are not familiar with the halting problem, I will not go into
it in detail [snip]

Well, if you need power for the computer you run your program on, I have a
really neat perpetual motion machine you can use.

Ooooh! Throw in a bridge (perhaps an 1883 model) and you got a deal!

!
--ag

--
Artie Gold -- Austin, Texas

"Yeah. It's an urban legend. But it's a *great* urban legend!"

[Andrew Koenig]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:3c**************************@posting.google.c om...

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a fallacy built
on the assumption of mythical infinite all powerfull machines. In
reality we deal with finite machines that are capable of two states in
a loop, they either terminate, or repeat themselves. In the mythical
halting problem scenario machines are saposed to have a third state
where they never repeat themselves... still they teach this problem
to kids in school as a kind of dogma so when they see the following
code it will often times be some what of a suprise.

It's only a surprise if your reasoning is naive.

It should be obvious that any program that uses a finite amount of memory
must also terminate, because if memory is finite, the number of memory
states is also finite, and once the program has exhausted them all, it must
start repeating.

It should also be obvious that any program that terminates must use only a
finite amount of memory, because its termination means that it does only a
finite number of operations, and each operation can affect only a finite
amount of memory.

Therefore, claiming that a program uses a finite amount of memory is
equivalent to claiming that it terminates.

In other words, when you say

In reality we deal with finite machines

you are really saying

In reality we deal with programs that terminate

so it should come as no surprise that if you are dealing only with programs
that terminate, you have no difficulty deciding whether or not they
terminate.
As it happens, though, the foregoing discussion has little to do with the
halting problem. You are essentially saying the following:

Give me a machine, and a program to run on that machine, and I will
(eventually) tell you whether that program will terminate.

The halting problem, however, is better phrased this way:

If I give you a program, can you tell me whether it is possible to build
a machine big enough so that it is possible to run that program without
exhausting the machine's memory?

Your infinite-loop detection technique is not capable of answering that
question, and it is precisely that question that the halting problem
addresses.

Moreore, it is not necessary to assune the existence of an infinite machine
for the halting problem to be relevant. Every program that halts is capable
of being executed on some machine or other -- it is merely a matter of
providing enough capacity and waiting long enough. The only question is
whether it is always possible to determine in finite time whether a
particular program will exceed the capacity of *every* machine one might
possibly build. And the answer to that question is no.

The proof is really quite simple. Suppose you give me a program named, say,
DoesItHalt, with the property that for any program P and input X,
DoesItHalt(P,X) returns "true" if P(X) would halt and "false" if it would
not. Then consider this program:

bool H(F) {
if (DoesItHalt(F, F))
return !F(F);
else
return false;
}

What is the value of H(H)? Let's see what happens.

First, we evaluate DoesItHalt(H,H). Let's assume that the result is true.
Then by the definition of DoesItHalt, H(H) must halt. Our function
evaluates H(H), which halts, and returns the opposite. So calling H(H)
returns !H(H), which is a contradiction.

Therefore, apparently, H(H) must not halt. But then DoesItHalt(H,H) had
better return false, otherwise DoesItHalt is broken. If it returns false,
then H(H) returns false as well, which means that H(H) terminates, which is
also a contradiction.

In other words, if we assume that DoesItHalt exists, we get a contradiction.
Therefore, DoesItHalt cannot exist.

It's really that simple.

[Alf P. Steinbach]

* "Andrew Koenig" <ar*@acm.org> schriebt:

Therefore, claiming that a program uses a finite amount of memory is
equivalent to claiming that it terminates.
Uhm, Andrew?
int main(){for(;;){}}
I claim (1) this program uses a finite amount of memory, and (2) that it
does not terminate.

It's really that simple.

A thread by 'Gremlin', with more speling mistaks than words, cross-posted
to [alt.magick.virtual-adepts], yes, it really is simple. ;-)

Perhaps <url: http://www.winternet.com/~mikelr/flame11.html>? Not sure.

[Andrew Koenig]

"Alf P. Steinbach" <al***@start.no> wrote in message
news:40***************@news.individual.net...

* "Andrew Koenig" <ar*@acm.org> schriebt:

Therefore, claiming that a program uses a finite amount of memory is
equivalent to claiming that it terminates.

Uhm, Andrew?
int main(){for(;;){}}
I claim (1) this program uses a finite amount of memory, and (2) that it
does not terminate.

Sorry -- I meant terminates or repeats a previous state, which is the sense
in which "terminates" was being used in the original posting.

[Gremlin]

"Andrew Koenig" <ar*@acm.org> wrote in
news:xT*********************@bgtnsc05-news.ops.worldnet.att.net:

"Alf P. Steinbach" <al***@start.no> wrote in message
news:40***************@news.individual.net...

* "Andrew Koenig" <ar*@acm.org> schriebt:

>
> Therefore, claiming that a program uses a finite amount of memory
> is equivalent to claiming that it terminates.

Uhm, Andrew?
int main(){for(;;){}}
I claim (1) this program uses a finite amount of memory, and (2) that
it does not terminate.

Sorry -- I meant terminates or repeats a previous state, which is the
sense in which "terminates" was being used in the original posting.

Sorry I wasn't able to understand your post, but I gather you believe there
is a program that can run on finite machines that will never terminate or
repeat? Or at least a program that you can't tell if it does either... If
that is so please post the program and I will try to code into it a
infinite loop detector.

[Claudio Puviani]

"Gremlin" <Gr*****@hotmail.com> wrote

Sorry I wasn't able to understand your post, but I gather you believe there
is a program that can run on finite machines that will never terminate or
repeat? Or at least a program that you can't tell if it does either... If
that is so please post the program and I will try to code into it a
infinite loop detector.

Here's a simple case: you have a stream of infinite length (if you don't think
this is possible, consider things like irrational numbers or inputs from real
time data acquisition) containing integer values. You're looking for a sequence
of values of length N within that stream (for example, looking for the sequence
'1234567890' in the fractional part of Pi). The sequence may or may not exist in
the stream.

You cannot -- C A N N O T -- choose an arbitrary point X, no matter how big, and
say "if I reach this point, it means the loop is infinite" because the sequence
might start at position X+1. You can decide that you want to give up after a
certain amount of time, but that is NOT the same thing as detecting an infinite
loop.

Claudio Puviani

[Nick Hounsome]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

"Andrew Koenig" <ar*@acm.org> wrote in
news:xT*********************@bgtnsc05-news.ops.worldnet.att.net:

"Alf P. Steinbach" <al***@start.no> wrote in message
news:40***************@news.individual.net...

* "Andrew Koenig" <ar*@acm.org> schriebt:
>
> Therefore, claiming that a program uses a finite amount of memory
> is equivalent to claiming that it terminates.

Uhm, Andrew?
int main(){for(;;){}}
I claim (1) this program uses a finite amount of memory, and (2) that
it does not terminate.
Sorry -- I meant terminates or repeats a previous state, which is the
sense in which "terminates" was being used in the original posting.

Sorry I wasn't able to understand your post, but I gather you believe

there is a program that can run on finite machines that will never terminate or
repeat? Or at least a program that you can't tell if it does either... If that is so please post the program and I will try to code into it a
infinite loop detector.

I repeat my previous point:

You have miss interpreted the halting problem - It doesn't say that you
can't do what
you are saying here - it says you can't write a program IN ADVANCE
that will be able to determine whether ANY program SUBSEQUENTLY submitted to
it will
terminate.

[Andrew Koenig]

"Gremlin" <Gr*****@hotmail.com> wrote in message
news:Xn******************@216.168.3.44...

Sorry I wasn't able to understand your post, but I gather you believe there is a program that can run on finite machines that will never terminate or
repeat? Or at least a program that you can't tell if it does either... If that is so please post the program and I will try to code into it a
infinite loop detector.

No, you gather incorrectly.

If you can't understand my post, then I'm afraid there's not much more to
say.

[Karl Heinz Buchegger]

Gremlin wrote:

If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not.

That's not the halting problem.
The halting problem is to write a program which analyzes
another program and decides if that program will halt in any
case, no matter what input that other program receives.
--
Karl Heinz Buchegger
kb******@gascad.at

[Karl Heinz Buchegger]

Gremlin wrote:

Johannes Bauer <df***********@gmx.de> wrote in
news:i1***********@laptophost.laptopdomain:

Gremlin wrote:

that's because my code had a few buggs in it.
I forgot to declare bool infinite, and needed to add some brakets
around one if statement.

Ehrm, no, it ain't. If you read my post, you'll see I fixed exactly
those things.

The whole problem is that your infinite loop detector does not detect
infinite loops, but detects finite loops with more than n iterations.
This is a bad appoach to the problem, as mentioned by dozens of people
in this very thread.

Greetings, Joe

The only time that my program will detect anything is in the case of the
loop being infinite. It doesn't detect n iterations it detects when one
counter moving twice as fast as another counter is equal to the other
counter. This occurance only occurs when the loop is infinite,

.... or if the solution to a problem takes more then n steps.
But you don't know that the loop will run forever. All you
know is that you didn't took enough steps to reach up with
a solution (if it exists at all).

--
Karl Heinz Buchegger
kb******@gascad.at

[Karl Heinz Buchegger]

Gremlin wrote:

red floyd <no*****@here.dude> wrote in
news:eM*******************@newssvr25.news.prodigy. com:

Because you're misinterpreting. You're not detecting an infinite loop,
you're detecting recurrence of data.

Also, the Halting Problem is not if a program can detect if it is in an
infinite loop itself, but whether a different program/UTM/whatever,
given program P as input, can say "P halts".

You post an infnite loop and I will post the same loop back, with an
infinite loop detector of this sort added to it that will detect your loop.
Some problems may not theoretically run in infinite loops but would of
course on a computer, the halting problem deals with theoretical problems
not reality.

#include <iostream>

using namespace std;

void foo( int n, int a, int b, int c )
{
if( n == 1 )
cout << n << " " << a << "->" << b << endl;
else {
foo( n-1, a, c, b );
cout << n << " " << a << "->" << b << endl;
foo( n-1, c, b, a );
}
}

int main()
{
int i;

cin >> i;

foo( i, 1, 2, 3 );

return 0;
}

no matter how you formulate your termination criterion (based
on some counting), I will always be able to feed an input number
which makes your test yell for an infinite loop, yet the above
will always terminate. It does so even if it takes longer then
the universe already exists.

--
Karl Heinz Buchegger
kb******@gascad.at

[00:00:00HG]

On Sat, 28 Feb 2004 23:31:44 +0000, Andrew Koenig wrote:

It should be obvious that any program that uses a finite amount of memory
must also terminate, because if memory is finite, the number of memory
states is also finite, and once the program has exhausted them all, it must
start repeating.

Mobius linking to a stack makes memory infinite as unused blocks
are recycled into the master stack. The only way to express the
infinite from within the finite is by conjecture.

Of course the only limitation to understanding the concept of limits
is that of makeing rules. When you imply the infinite there can be no
rules and you are always bound to the question of limits. When it comes
to theory one can break that bond by not allowing subjective rules.

More discoveries have been made by rule breakers than not. That's
what inventivness is, ignoring the 'No Tresspassing' signs others
have errected to discourage competition.

[00:00:00HG]

On Sat, 28 Feb 2004 23:31:44 +0000, Andrew Koenig wrote:

It should be obvious that any program that uses a finite amount of memory
must also terminate, because if memory is finite, the number of memory
states is also finite, and once the program has exhausted them all, it must
start repeating.

Mobius linking to a stack makes memory infinite as unused blocks
are recycled into the master stack. The only way to express the
infinite from within the finite is by conjecture.

Of course the only limitation to understanding the concept of limits
is that of makeing rules. When you imply the infinite there can be no
rules and you are always bound to the question of limits. When it comes
to theory one can break that bond by not allowing subjective rules.

More discoveries have been made by rule breakers than not. That's
what inventivness is, ignoring the 'No Tresspassing' signs others
have errected to discourage competition.

[00:00:00HG]

On Sat, 28 Feb 2004 23:31:44 +0000, Andrew Koenig wrote:

It should be obvious that any program that uses a finite amount of memory
must also terminate, because if memory is finite, the number of memory
states is also finite, and once the program has exhausted them all, it must
start repeating.

Mobius linking to a stack makes memory infinite as unused blocks
are recycled into the master stack. The only way to express the
infinite from within the finite is by conjecture.

Of course the only limitation to understanding the concept of limits
is that of makeing rules. When you imply the infinite there can be no
rules and you are always bound to the question of limits. When it comes
to theory one can break that bond by not allowing subjective rules.

More discoveries have been made by rule breakers than not. That's
what inventivness is, ignoring the 'No Tresspassing' signs others
have errected to discourage competition.

[00:00:00HG]

On Sat, 28 Feb 2004 23:31:44 +0000, Andrew Koenig wrote:

It should be obvious that any program that uses a finite amount of memory
must also terminate, because if memory is finite, the number of memory
states is also finite, and once the program has exhausted them all, it must
start repeating.

Mobius linking to a stack makes memory infinite as unused blocks
are recycled into the master stack. The only way to express the
infinite from within the finite is by conjecture.

Of course the only limitation to understanding the concept of limits
is that of makeing rules. When you imply the infinite there can be no
rules and you are always bound to the question of limits. When it comes
to theory one can break that bond by not allowing subjective rules.

More discoveries have been made by rule breakers than not. That's
what inventivness is, ignoring the 'No Tresspassing' signs others
have errected to discourage competition.