From: Vladimir Nesov (robotact@gmail.com)
Date: Tue Oct 13 2009 - 11:03:31 MDT
On Tue, Oct 13, 2009 at 8:38 PM, John K Clark <johnkclark@fastmail.fm> wrote:
>
> Obviously if a computer has a finite memory it would be possible in
> theory to keep a record of every state the machine goes into, and if you
> found that a state was repeated then you'd know for sure that the
> machine was in a infinite loop. But the trouble is that the machine
> needed to do all that checking would have to be much larger than the
> original machine, and that larger machine would have no way to know if
> it was itself in a infinite loop unless it was watched over by an even
> larger machine.
>
So far in this discussion, the above seems to be the most technically
precise incorrect assertion you've made. Until you take it back, it
serves as a reference example of your incompetence.
(That is, a program that halts immediately does halt, nothing
impossible about that; similarly, a specific algorithm that runs for
at most X steps, in the meantime checking a transition system for
loops or whatever, does stop after than number of steps.)
-- Vladimir Nesov
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:04 MDT