W
Walter Roberson
Could you elaborate on what is "The Halting Problem". I'm not able to
remember it, but I did hear of it some time back.
Suppose you have program source X available as input ("source" can
include machine language in this context), and you want to determine
whether that program will eventually terminate for all possible inputs
to X, or if X instead might infinite loop on -some- possible input.
Can you write a program H which will read the source X
and tell you whether X will always terminate (or to use another term,
whether X will always halt)?
If you are given X ahead of time, you might be able to write your
halting test program H to determine whether that one program X will
ever halt, and that same program H might work for some other programs
that are very similar to X. With a really clever program H and a big
enough computer, you might even be able to handle a lot of different
programs -- you might even be able to properly answer the question
for trillions of different possible input programs. It turns out,
though, that it is IMPOSSIBLE to write your halting test program H
to handle *all* possible input programs.
If you had an executable image and you knew the exact format of the
image, and if the format told you exactly where the instruction
sequence started and stopped, and if the machine/OS strictly disallowed
executing data, and if you could *reliably* tell what all the
instructions were (i.e., it was somehow impossible to branch into the
"middle" of an instruction), then you could do a mechanical search to
determine whether there was a RETURN instruction somewhere in the
executable stream... but figuring out whether some RETURN will always
be -reached- is *much* harder.
If the machine/OS does allow data to be executed, then again the
problem becomes hard, because you would need to determine whether the
program ever -writes- a RETURN instruction into a location that it will
definitely execute.
If the machine allows you to branch into the middle of an instruction
byte sequence and the machine allows branch addresses to be calculated
then the problem is difficult again, because you would have to figure
out whether a byte sequence that happens to have the same value as
the RETURN instruction might ever be reached by an unusual branch.
For example, if the RETURN instruction is 83 and if "left shift
address register #8 by 3 bits" happens to be 27 83, then the 83
is just "random chance" if you execute in a straight forward manner,
but if there happens to be a branch to the byte past the 27 then
suddenly there's your RETURN instruction. (And it's not as simple
as that, even -- the branch might be to an unexpected boundary somewhere
hundreds of bytes before and all of the reinterpreted instructions
just happen to come out such that the 27 is part of a previous
instruction in the new execution, eventually leading to the 83 RETURN...)
To expound a bit further: your original question was wide open
and did not place any restrictions as to specific executable format,
machine language, amount of machine memory, available hard disk space,
and so on. That made the question equivilent to asking, "Is it
always possible to do this?", and as I discussed briefly above, the
answer to "always possible?" is NO, even though you might be able to
answer properly for trillions of different executables.
If you pin down to one *particular* set of machine specifications, and
place a fixed pre-determined limit on the amount of memory available to
the program that is to be tested, then the answer reverses itself and
becomes YES: for any pre-specified fixed-resource deterministic
computer system, you *can* always answer the question of whether a
given input program {that is within the pre-specified resource limits}
will always halt or not.
The difficulty, though, is that if the program to be examined is
allowed to use M resource slots (e.g., M bytes of memory including
machine registers), and if each of the resource slots can have S
different states (e.g., each 8-bit byte can represent any of 256
different values), then the resources needed for the testing program
would be at least S**(M-1) resource slots where ** indicates
exponentiation. For example, if the programs to be tested were
restricted to a mere 64 Kbyte of memory, then the testing program would
need access to at least 8**65535 bytes of memory... which is a number
more than 59000 digits long. And there isn't that much memory in the
universe [If you were to use every elementary particle in the
universe and were able to extract 2 bits of information from each
of them, then you would be able to run halting tests on programs
that had access to about 34 bytes of memory. With a gigabyte of
memory, you'd be able to run halting tests on programs that
had access to about 12 bytes of memory.]