On Fri, Jan 25, 2008 at 09:09:43AM -0800, Darren New wrote:
David Brown wrote:
but even on a severely bounded machine,
there is no practical solution.
Prove it.
Well, here's part of a proof.
1. I define impractical as where the solution to any non-trivial input
size requires more storage than the size of the universe or more time
than the duration of the known universe.
2. Given a processing system with 'n' bits of memory. Each processing
step modifies zero or more of these bits. Halting is defined as a
processing step that modifies zero bits. The processing system has no
other state.
3. Because there are a finite number of states, it is sufficient to
detect a repeated state to detect a non-halt. I know of two ways of
detecting loops (but I don't know how to prove there aren't more):
a. Track all visited states. There are 2^(2^n) possible states. This
requires impractical storage for all non-trivial n.
b. Run two identical systems from the same starting system, but run
one two steps for each step of the first. If they ever reach the same
state, there is a cycle, and the system will not halt. This requires
2*2^n storage. But, the longest possible cycle would go through every
state, requiring 2^(2^n) steps. This requires impractical time.
I suspect 3a and 3b can be proven by contradiction. It also necessary to
prove that the repeat detection of 3 is necessary instead of merely
sufficient.
David
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
