Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!ncar!gatech!usenet.ins.cwru.edu!eagle!data.nas.nasa.gov!sun418.nas.nasa.gov!truesdel
From: truesdel@nas.nasa.gov (David A. Truesdell)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <truesdel.673916303@sun418>
Date: 10 May 91 22:58:23 GMT
References: <2990@optima.cs.arizona.edu> <1991May10.155454.2239@maths.nott.ac.uk> <3125@cirrusl.UUCP>
Sender: news@nas.nasa.gov
Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA
Lines: 44

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