[Theory] Halting problem

[%u]

== Quote from Stewart Gordon (smjg_1998 at yahoo.com)'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 ;)