[racket] Checking infinite loops

  Hi Patrick,

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:

int i = 0;
while(true) { i = i+1; }

never hits a duplicate state, because i never rolls over.

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.

- Tim

On 10/4/2010 10:31 AM, Patrick Li wrote:
> I know of the halting problem but can't figure out this dilemma.
>
> Imagine you load a program into a virtual machine.
>
> This virtual machine has no registers. All operations are done through 
> the memory.
>
> That is, the entire state of the virtual machine is captured by 
> whatever is in memory.
>
> In that case, because machines are deterministic, the next operation 
> that the machine takes is completely determined by the current state 
> it is in.
>
> 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?
>
>   -Patrick
>
> On Mon, Oct 4, 2010 at 10:02 AM, Stephen Bloch <sbloch at adelphi.edu 
> <mailto:sbloch at adelphi.edu>> wrote:
>
>
>
>     On Oct 4, 2010, at 8:37 AM, Eric Tanter <etanter at dcc.uchile.cl
>     <mailto:etanter at dcc.uchile.cl>> wrote:
>
>     > Just for the sake of precision:
>     >
>     > On Oct 3, 2010, at 11:48 PM, Stephen Bloch wrote:
>     >> 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 "in ANY language" is too much: This is true of any _Turing
>     complete_ language.
>
>     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.
>
>     Stephen Bloch
>     sbloch at adelphi.edu <mailto:sbloch at 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101004/b556f551/attachment.html>