Yep, but the state space is a wee bit large to record :-). (All computers are equivalent to finite automata in theory, but definitely not in practice!)
Ed On Mon, Oct 04, 2010 at 10:31:36AM -0400, 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 <[1]sbl...@adelphi.edu> > wrote: > > On Oct 4, 2010, at 8:37 AM, Eric Tanter <[2]etan...@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 > [3]sbl...@adelphi.edu > _________________________________________________ > �For list-related administrative tasks: > �[4]http://lists.racket-lang.org/listinfo/users > > References > > Visible links > 1. mailto:sbl...@adelphi.edu > 2. mailto:etan...@dcc.uchile.cl > 3. mailto:sbl...@adelphi.edu > 4. http://lists.racket-lang.org/listinfo/users > _________________________________________________ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/users
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
