Path: utzoo!utgpu!attcan!uunet!lll-winken!ames!mailrus!cornell!rochester!rit!cci632!ccicpg!nick
From: nick@ccicpg.UUCP (Nick Crossley)
Newsgroups: comp.lang.c
Subject: Re: The Halting Problem (was: YALF (yet another lint foulup))
Summary: You can check specific programs
Message-ID: <8316@ccicpg.UUCP>
Date: 13 Jan 89 18:39:21 GMT
References: <9255@smoke.BRL.MIL> <379@lakart.UUCP> <9341@ihlpb.ATT.COM> <9371@ihlpb.ATT.COM> <2686@ficc.uu.net> <47306@yale-celray.yale.UUCP> <47372@yale-celray.yale.UUCP> <47406@yale-celray.yale.UUCP>
Reply-To: nick@ccicpg.UUCP (Nick Crossley)
Organization: CCI CPG, Irvine CA
Lines: 32

In article <47406@yale-celray.yale.UUCP> wald-david@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@ccicpg.UUCP