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 <sbl...@adelphi.edu
<mailto:sbl...@adelphi.edu>> wrote:
On Oct 4, 2010, at 8:37 AM, Eric Tanter <etan...@dcc.uchile.cl
<mailto: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
sbl...@adelphi.edu <mailto:sbl...@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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
