Thanks for explaining that to me. I never actually looked up the formal definition of Turning-Completeness before.<div><br></div><div>So this seems rather positive. Through some clever search algorithms, or heuristics, we can have a infinite-loop checker that works well enough in practice.</div> <div><br></div><div> -Patrick<br><br><div class="gmail_quote">On Mon, Oct 4, 2010 at 10:55 AM, Eric Tanter <span dir="ltr"><<a href="mailto:etanter@dcc.uchile.cl">etanter@dcc.uchile.cl</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> right ;)<br> <br> -- Éric<br> <div><div></div><div class="h5"><br> <br> On Oct 4, 2010, at 10:02 AM, Stephen Bloch wrote:<br> <br> ><br> ><br> > On Oct 4, 2010, at 8:37 AM, Eric Tanter <<a href="mailto:etanter@dcc.uchile.cl">etanter@dcc.uchile.cl</a>> wrote:<br> ><br> >> Just for the sake of precision:<br> >><br> >> On Oct 3, 2010, at 11:48 PM, Stephen Bloch wrote:<br> >>> 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.<br> >><br> >> The "in ANY language" is too much: This is true of any _Turing complete_ language.<br> ><br> > Even more precisely, this is true if the language of the program being analyzed is Turing complete. The language in which you write the alleged analyzer doesn't matter, as long as it can be called from a Turing-complete language.<br> ><br> > Stephen Bloch<br> > <a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a><br> <br> _________________________________________________<br> For list-related administrative tasks:<br> <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a><br> </div></div></blockquote></div><br></div>