== Quote from Stewart Gordon ([email protected])'s article > On 13/10/2010 00:23, %u wrote: > <snip> > > Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n > > that is). > > But those two system could of course be on the same computer. My computer, > > for > > instance, can run Halt.exe on 30bit programs :D > n2^n? Are you sure? > Here's how I worked it out. Let P be the program being analysed, and H > be the program that does the halt analysis. > The only bits of information H needs to store are: > - the code of P > - the state P is in at the moment > - whether P has so far visited each possible state > The last of these is usually what takes up most of the space. If P is > limited to n bits of memory, there are 2^n possible states. Whether a > state has been visited is a boolean value, therefore we need only 2^n > bits for the entire table. We don't need to store up the bit patterns > of these states - which state each bit refers to is evident from its > address in H's memory space. You are totally right, I took the "store the state" a bit too literal. This now makes my hatl.exe capable of 33bit programs :D
> You could take this as meaning that the halting problem is solvable > within a certain computational class: that in which a finite but > arbitrarily large amount of memory must be allocated at the outset. > However, we would need to allow the amount of memory to allocate to be a > function of the input, which again leads to a problem: when you try to > run H on itself, it will need more memory than itself, so the > calculation would infinitely recurse. The idea was that we had two systems; A(max n bits) and B(min 2^n bits) but never did I want to suggest that system A could fix its own HP nor that B could fix its HP(you would need system C for that), only that those two systems could sit on the same computer and that A's HP can be done by B. B's halting program only accepts A-size inputs. I never wanted to counter the statement that you need a "stronger" system to do the HP of the "weaker"one, only clarify the meaning of system. > So essentially, two computational classes are involved: the one FOR > which you are solving the halting problem, and the one IN which you are > solving the halting problem. > Stewart. Exactly ;)
