begin quoting David Brown as of Fri, Jan 25, 2008 at 10:03:54AM -0800: > 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.
I think you're going to have a problem because you don't constrain what "severely bounded" means. We're no longer talking turing machines; if we bound our machine to run only primitive recursive programs, we're can make confident judgements about the machine halting in fixed time. Other ways of "severely bounding" the machine may also offer "practical" solutions. > 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. Duration is meaningless without a performance limit. More bits than the current estimated size of the universe is a better yardstick, but even then you're making assumptions as to how the target scheme will run. > 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. Don't we also need to define input? I would think that our bounded machine could be described with a DFA operating on a symbol set of size 1 and an unbounded input string (the clock). We need to keep the input separate so that our program is general, yes? > 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. There may be clever ways around that. > 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. Take the trivial machine that halts. The trailing machine will have the same bit-pattern as the leading machine, and flag a cycle, despite no state changing ever. Special consideration needs to be taken for the initialization. > I suspect 3a and 3b can be proven by contradiction. "Assume that with storage of fixed size Q, we can detect a duplicate state in 2^2^n states."? Hm. Perhaps. > It also necessary to > prove that the repeat detection of 3 is necessary instead of merely > sufficient. I can see why that would help, but why would that be true? -- No offense -- it's not that I disbelieve you, But your argument has some convincing to do. Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
