Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!sdd.hp.com!wuarchive!udel!ee.udel.edu
From: new@ee.udel.edu (Darren New)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <53143@nigel.ee.udel.edu>
Date: 9 May 91 18:53:14 GMT
References: <2990@optima.cs.arizona.edu> <1991May9.122526.13533@s1.msi.umn.edu>
Sender: usenet@ee.udel.edu
Organization: University of Delaware
Lines: 21
Nntp-Posting-Host: estelle.ee.udel.edu

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