🚀 go-pugleaf

This is an interesting discussion, and I have learned a lot from it.
There are quite a few subtle points that I had not realized before.

gudeman@cs.arizona.edu (David Gudeman) writes:

>If you have three C-machines M1, M2 and M3 you can form a compound
>machine M1->M2;M3 with the behavior that if M1 terminates in an
>accepting state then M2 is executed on the remainder of the input, and
>if it terminates in a rejecting state then M3 is executed on the
>remainder of the input.
....[ stuff deleted ] .....
>Computer programs certainly meet the 3 criteria in the theorem, so it
>is not possible to write a computer program that solves the halting
>problem for computer programs.

The problem here is that if you are dealing with a specific machine,
with one particular piece of hardware, then the description of M1 may
fill up the machine, and likewise with M2 and M3. In that case you may
very well have no room to store the description of M1->M2;M3. I think
this is Victor Yodaiken's point, or at least one of them. It's no use
saying you will put the description on tape because that can get too
large as well. If the number of tapes is larger than the memory of the
computer you will almost certainly be in trouble.

The discussion is quite difficult, because on the one hand we are
working with abstract constructs and mathematical proofs, and on the
other hand with practical computers. To relate the two, we make a
mathematical model of the computer. But mathematical models are never
fully accurate descriptions. For example, I never have to call out an
engineer to fix my finite state automaton :-). And I don't have to
worry about the effect of gamma rays on it, nor about how the end of
the universe may affect it. We have therefore to choose, from among
various possible mathematical models, not the model which *IS* the
computer, but the model which most faithfully follows the particular
behaviour we are trying to investigate. This is a matter of judgement, not
of irrefutable logic, and is
likely to depend on which kind of behaviour of the practical computer one is
interested in. If you are interested in error correction in hardware,
your mathematical model is not going to be a finite state automaton,
because that never makes errors.

>Proof: Suppose that Halt exists.  Then define 
>    Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept
>what is the result of running Paradox?

Is this a misprint, David? You can't define Paradox in terms of
itself. If it is a misprint, can you please repost, as I would like to
study this.

			David Epstein.

In article <1991May9.122526.13533@s1.msi.umn.edu> dbae@s1.msi.umn.edu (David Epstein) writes:
>>Proof: Suppose that Halt exists.  Then define 
>>    Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept
>>what is the result of running Paradox?
>
>Is this a misprint, David? You can't define Paradox in terms of
>itself. If it is a misprint, can you please repost, as I would like to
>study this.

Paradox is not really defined in terms of itself in a recursive-call sense.
E(Paradox) is the "source code" for the program Paradox. If you know how
Halt, CLoop, and CAccept are written, then you know how Paradox is
written (see the >> lines :-).  Feed the Paradox program to Halt, and
if Halt says it halts then loop, otherwise halt. Paradox never explicity
calls itself (altho Halt might "call" Paradox in some way, in which case 
Halt doesn't halt and thus gives a "wrong" answer).

-- 
--- Darren New --- Grad Student --- CIS --- Univ. of Delaware ---
----- Network Protocols, Graphics, Programming Languages, FDTs -----
+=+ Nails work better than screws, when both are driven with hammers +=+

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

In <1991May10.155454.2239@maths.nott.ac.uk> anw@maths.nott.ac.uk (Dr A.
N. Walker) writes:

>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

Suppose jim.c halts when given certain inputs and does not halt when
given certain other inputs.  The halting problem in this case has not
been correctly defined, since the command line "fred jim.c" does not
specify the inputs given to jim.c.  We we really ought to be saying

     % fred jim.c fred.c

where jim.c is the program whose halting characteristics are being
tested, and fred.c is the input that jim.c will be assumed to read when
it executes.
--
Rahul Dhesi <dhesi@cirrus.COM>
UUCP:  oliveb!cirrusl!dhesi

For the moment, lets assume our analysis routine manages to place a bound
on the number of states (size of memory) that will exist in the compiled
program and that the analysis program must itself execute within the same
finite-state machine. Because the analysis routine must itself be coded
in some of the states, it does not have enough states to represent the
states of the program it is analysing. Is there any hope (in a theoretical
sense) of a finite state machine computing interesting properties of
an arbitrary finite state machine of its own size?

  Ken Walker / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721
  +1 602 621-4252  kwalker@cs.arizona.edu {uunet|allegra|noao}!arizona!kwalker

dhesi%cirrusl@oliveb.ATC.olivetti.com (Rahul Dhesi) writes:

>In <1991May10.155454.2239@maths.nott.ac.uk> anw@maths.nott.ac.uk (Dr A.
>N. Walker) writes:

>>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

>Suppose jim.c halts when given certain inputs and does not halt when
>given certain other inputs.  The halting problem in this case has not
>been correctly defined, since the command line "fred jim.c" does not
>specify the inputs given to jim.c.  We we really ought to be saying

>     % fred jim.c fred.c

>where jim.c is the program whose halting characteristics are being
>tested, and fred.c is the input that jim.c will be assumed to read when
>it executes.

And therein lies the madness:
The next step is:

    % fred jim.c fred.c jim.c

Then:

    % fred jim.c fred.c jim.c fred.c

Then:

    % fred jim.c fred.c jim.c fred.c jim.c ...

And so on.  Thus, the "run it, and see if it halts" suggestion falls flat on
its face.  There is at least one problem which would take an infinite amount of
time and resources to set up, much less attempt to run.
--
T.T.F.N.,
dave truesdell (truesdel@nas.nasa.gov)
'And Ritchie said, "Let there be portability!"  And nothing happened, so
 Ritchie realized that he had his work cut out for him.'

Kenneth Walker:
   Is there any hope (in a theoretical sense) of a finite state
   machine computing interesting properties of an arbitrary finite
   state machine of its own size?

I don't think this is an interesting question.  :-)

An interesting question would be:  what properties should a
computation device have such that most practical programs can be
determined to halt.

This is related to proving a program correct.

I should note that functional languages seem to be rather promising
in this regard.

Raul Rockwell

In article <truesdel.673916303@sun418> truesdel@nas.nasa.gov
(David A. Truesdell) writes:
>dhesi%cirrusl@oliveb.ATC.olivetti.com (Rahul Dhesi) writes:
>>Suppose jim.c halts when given certain inputs and does not halt when
>>given certain other inputs.  The halting problem in this case has not
>>been correctly defined, since the command line "fred jim.c" does not
>>specify the inputs given to jim.c.

	Quite right, but the distinction is uninteresting, because all
interesting [:-)] variants of the halting problem are equally insoluble.
E.g., it is generally undecidable whether "jim.c" halts when given *no*
input, when given *specified* input, when given *some* input or when
given *any* input.  In my original submission, I carefully left all this
to the reader!

>>				      We we really ought to be saying
>>     % fred jim.c fred.c
>
>And therein lies the madness:
>The next step is:
>
>    % fred jim.c fred.c jim.c
>
>Then:
>
>    % fred jim.c fred.c jim.c fred.c
>
>Then:

	Then you define "fred" to [attempt to] determine whether its
parameter halts or loops *when given itself* as input, and the paradox
comes back and bites you again without Rahul's objection.  See Minsky,
op previously cit, for a full discussion.

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