Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ukc!strath-cs!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: <1991May13.171951.9955@maths.nott.ac.uk>
Date: 13 May 91 17:19:51 GMT
References: <2990@optima.cs.arizona.edu> <1991May10.155454.2239@maths.nott.ac.uk> <3125@cirrusl.UUCP> <truesdel.673916303@sun418>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 37

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