[Theory] Halting problem

[Stewart Gordon]

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.