Thanks for explaining that to me. I never actually looked up the formal definition of Turning-Completeness before.
So this seems rather positive. Through some clever search algorithms, or heuristics, we can have a infinite-loop checker that works well enough in practice. -Patrick On Mon, Oct 4, 2010 at 10:55 AM, Eric Tanter <etan...@dcc.uchile.cl> wrote: > right ;) > > -- Éric > > > On Oct 4, 2010, at 10:02 AM, Stephen Bloch wrote: > > > > > > > On Oct 4, 2010, at 8:37 AM, Eric Tanter <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 > > _________________________________________________ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/users >
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
