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 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.
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.
