Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!uakari.primate.wisc.edu!samsung!uunet!mcsun!ukc!warwick!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <1991May10.155454.2239@maths.nott.ac.uk>
Date: 10 May 91 15:54:54 GMT
References: <2990@optima.cs.arizona.edu>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 68

In article <2990@optima.cs.arizona.edu> gudeman@cs.arizona.edu
(David Gudeman) writes:
>(I didn't want to go to this much work, but no one else has pointed
>this out, so here goes.)

	I was intending to, but news takes *ages* to get here, so I was
too late ....

	Anyway, I think I still have something to say.  As David says,
the halting problem really isn't a problem of large machines.  I like to
think in more concrete terms than these abstract machines with inputs over
Sigma and so on, so here is the same argument more concretely.

	Suppose you write a [purported] halting problem solver.  I'll
assume it's in C, so you have a program source called, say, "fred.c",
which compiles into a binary program "fred", running under Unix.  The
idea is that you call

	$ fred jim.c

and the computer clunks away for a while, and then prints out "Halts"
if "jim.c" describes a program that eventually halts, and prints out
"Loops" if the program would run for ever.  Let us assume that the
structure of "fred.c" is such that it computes away for a while, but
eventually must run through a final chunk of code that looks like:

	if (halt)
		printf ("Halts\n");
	else
		printf ("Loops\n");
	exit (0);

I now subvert "fred" by writing a new program whose source is "bert.c",
identical with "fred.c" except that the above chunk is replaced by

	if (halt)
		while (1);	/* ie, loop forever */
	else
		exit (0);

Now, whenever "fred" would print "Halts", "bert" will loop forever,
and whenever it prints "Loops", "bert" stops.

	What does "bert bert.c" do?  It stops if "fred bert.c" would print
"Loops", and goes on forever if "fred bert.c" would print "Halts".  So,
"fred bert.c" cannot tell the truth.  There are three ways out of this:

	(a) "fred" can lie [but then it's not much use];
	(b) "fred" can go on for ever without printing anything [that's
		not much use either!];
	(c) "fred" can admit, after a while, that it cannot tell, and give up.

Note, however, that, in any sensible implementation, "bert" is, if anything,
rather simpler than "fred".  The conclusion is that the best we can hope for
from a "halting problem program" is for it to be able to analyse simple
programs, but that anything complicated will be beyond it.  In particular,
it cannot be powerful enough to introspect itself.  [Finding and curing
the bugs in the above argument is left as an exercise for the reader.]

	As David says, there is nothing particularly "large" in this
sort of argument.  The best source I know for all this material is
*still* Minsky's "Computation:  Finite and Infinite Machines", which
is now terribly out of date, but is brilliantly written.  A new edition
would be a delight.

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk