473,703 Members | 2,324 Online

# Infinite Loop Detector

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%1000000 0==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==tr ue)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!" <<endl;
return 0;
}
Jul 22 '05 #1
43 5582
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%1000000 0==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==tr ue)
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
Jul 22 '05 #2
#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%1000000 0==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==tr ue)
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*****@laptoph ost.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%1000000 0==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==tr ue)
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

Jul 22 '05 #3
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%1000000 0==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==tr ue)
cout<<"Infinite Loop..."<<endl;
else
cout<<"Halted!" <<endl;
return 0;
}

Jul 22 '05 #4
In article <3c************ **************@ posting.google. com>,
Gremlin <Gr*****@hotmai l.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%1000000 0==0){
cout << test<<endl;
cout << buf<<endl;
}
}
if(infinite==tr ue)
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.
Jul 22 '05 #5
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".
Jul 22 '05 #6
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...
Jul 22 '05 #7
red floyd <no*****@here.d ude> wrote in
news:eM******** ***********@new ssvr25.news.pro digy.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.
Jul 22 '05 #8

"Gremlin" <Gr*****@hotmai l.com> wrote in message
news:Xn******** **********@216. 168.3.44...
red floyd <no*****@here.d ude> wrote in
news:eM******** ***********@new ssvr25.news.pro digy.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

Jul 22 '05 #9
"Mike Wahler" <mk******@mkwah ler.net> wrote in

"Gremlin" <Gr*****@hotmai l.com> wrote in message
news:Xn******** **********@216. 168.3.44...
red floyd <no*****@here.d ude> wrote in
news:eM******** ***********@new ssvr25.news.pro digy.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?
Take this code for example.

int main(){
return 0;
}

it is equivalent to....

int main(){
//this is a comment
return 0;
}
Jul 22 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.