I know of the halting problem but can't figure out this dilemma.<div><br></div><div>Imagine you load a program into a virtual machine. </div><div><br></div><div>This virtual machine has no registers. All operations are done through the memory.</div> <div><br></div><div>That is, the entire state of the virtual machine is captured by whatever is in memory.</div><div><br></div><div>In that case, because machines are deterministic, the next operation that the machine takes is completely determined by the current state it is in.</div> <div><br></div><div>Therefore, can't the virtual machine detect whether a program will run forever by simply checking whether it's returned to a previously visited state?</div><div><br></div><div> -Patrick</div><div> <br><div class="gmail_quote">On Mon, Oct 4, 2010 at 10:02 AM, Stephen Bloch <span dir="ltr"><<a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div class="im"><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> </div>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> <div class="im"><br> Stephen Bloch<br> <a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a><br> _________________________________________________<br> </div><div><div></div><div class="h5"> 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>