<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type"> <title></title> </head> <body bgcolor="#ffffff" text="#000000"> Hi Patrick,<br> <br> The problem (Assuming I understand your message properly. :-) ) is that once you bound the memory, you no longer have a Turing-complete language. A program on my desktop machine can be expressed as a (very large) DFA. The halting problem for these DFAs is decidable (even if it might take years to solve). On the other hand, if there were no memory constraints, this code:<br> <br> int i = 0;<br> while(true) { i = i+1; }<br> <br> never hits a duplicate state, because i never rolls over.<br> <br> You can imagine running other algorithms on my example, but the mind-bending truth is that it takes an infinite number of such "corner case" algorithms to cover all possible programs.<br> <br> - Tim<br> <br> On 10/4/2010 10:31 AM, Patrick Li wrote: <blockquote cite="mid:AANLkTimsFobhwUsZixNaRScMnfT4qxvhs11zj+M4y6h9@mail.gmail.com" type="cite"> <meta http-equiv="Context-Type" content="text/html; charset=ISO-8859-1"> 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>On Mon, Oct 4, 2010 at 10:02 AM, Stephen Bloch <span><<a moz-do-not-send="true" href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a>></span> wrote:<br> <blockquote> <div><br> <br> On Oct 4, 2010, at 8:37 AM, Eric Tanter <<a moz-do-not-send="true" 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><br> Stephen Bloch<br> <a moz-do-not-send="true" href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a><br> _________________________________________________<br> </div> <div> <div>  For list-related administrative tasks:<br>  <a moz-do-not-send="true" href="http://lists.racket-lang.org/listinfo/users">http://lists.racket-lang.org/listinfo/users</a><br> </div> </div> </blockquote> </div> <br> </div> <pre wrap=""> <fieldset class="mimeAttachmentHeader"></fieldset> _________________________________________________ For list-related administrative tasks: <a class="moz-txt-link-freetext" href="http://lists.racket-lang.org/listinfo/users">http://lists.racket-lang.org/listinfo/users</a></pre> </blockquote> <br> </body> </html>