Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!uunet!stanford.edu!msi.umn.edu!dbae
From: dbae@s1.msi.umn.edu (David Epstein)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <1991May9.122526.13533@s1.msi.umn.edu>
Date: 9 May 91 12:25:26 GMT
References: <2990@optima.cs.arizona.edu>
Organization: Minnesota Supercomputer Institute
Lines: 50

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.