Perhaps the original poster was just asking for how to check for the occurrence of a loop in a graph, presumably in the context of traversing it.
At least that's how I understood his mail when I first read it -- now I'm no longer so sure. Best, Erich On Sun, 2010-10-03 at 23:48 -0400, Stephen Bloch wrote: > On Oct 3, 2010, at 7:19 PM, Marco Morazan wrote: > > > What year of study are you in? > > > > I will assume you are a beginner. It can't be done in Racket or any > > other programming language. Most Automata Theory books have a proof of > > that The Halting Problem is unsolvable. > > More precisely, you can write a program that will say "yes, there's an > infinite loop" whenever there's an infinite loop, but sometimes mistakenly > says "yes, there's an infinite loop" when there isn't. Or you can write a > program that will say "no, there's no infinite loop" whenever there isn't > one, but sometimes mistakenly says "no, there's no infinite loop" when there > is. Or you can write a program that never makes a mistake on this question, > but sometimes goes infinite itself. But there is NO program, in ANY > language, that takes in another program and always tells correctly (in finite > time) whether that other program contains an infinite loop. > > The proof is simple: suppose there were such a program; call it "inf-loop?". > Then I would write a program "diag" as follows: > > (define (diag) > (if (inf-loop? diag) > "bye now" > (diag))) > > Now, either "diag" goes infinite or it doesn't. If it does, (inf-loop? diag) > will return true (because that's what inf-loop? does), so the "if" will > return "bye now", thus NOT going into an infinite loop. On the other hand, > if "diag" doesn't go infinite, (inf-loop? diag) will return false (because > that's its job), so the "if" will call "diag", thus going into an infinite > loop. In short, if "diag" goes infinite, then it doesn't, and if it doesn't, > then it does. Both situations are impossible, so our assumption that > "inf-loop?" exists must have been incorrect. We conclude that "inf-loop?" > doesn't exist (or isn't always correct, or sometimes goes infinite itself, or > something). > > > Stephen Bloch > sbl...@adelphi.edu > > _________________________________________________ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/users _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
