[racket] Checking infinite loops

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> wrote:

>
>
> On Oct 4, 2010, at 8:37 AM, Eric Tanter <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
> _________________________________________________
>   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/1871e324/attachment.html>