The Halting Problem (was: YALF (yet another lint foulup))

[Nick Crossley]

In article <47406 at yale-celray.yale.UUCP> wald-david at CS.YALE.EDU (david wald) writes:
>Therefore, the only meaningful deterministic
>interpretation of the question "does the program halt" is "does the
>program halt, assuming its malloc()s never fail for lack of memory."
>...
>Either way, then, you cannot place a bound on the machine, so the
>halting problem for C programs remains undecidable.
>...

Now, it is a long time since I was taught this stuff, but I seem to recall one
point which has not yet been brought up.  The 'Halting Problem' is that it is
not possible to build a Turing machine which will read the description of
*any arbitrary* Turing machine and *any arbitrary* input, and decide whether
or not that Turing machine will halt given that input.

It is not necessarily impossible to decide whether or not a particular Turing
machine/program will halt.  Indeed, in many cases it is trivial to show that
they do, given any input:

	int main (void)  /* or (int argc, char *argv[]) whichever you like  */
	{
		return 0;
	}

Further, the problem in the general case is not that you might get the wrong
answer, it is just that your super checking program itself might not halt for
some program/input pairs.
-- 

<<< standard disclaimers >>>
Nick Crossley, CCI, 9801 Muirlands, Irvine, CA 92718-2521, USA. (714) 458-7282
uunet!ccicpg!nick  /  nick at ccicpg.UUCP