Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site harvard.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!genrad!panda!talcott!harvard!draves
From: draves@harvard.UUCP (Richard Draves)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <633@harvard.UUCP>
Date: Tue, 21-Jan-86 05:32:04 EST
Article-I.D.: harvard.633
Posted: Tue Jan 21 05:32:04 1986
Date-Received: Thu, 23-Jan-86 20:54:31 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> <438@faron.UUCP> <4101@kestrel.ARPA>
Reply-To: draves@harvard.UUCP (Richard draves)
Distribution: net
Organization: Aiken Comp Lab, Harvard
Lines: 32
Xref: watmath net.ai:3202 net.philosophy:3892

Say that a Turing Machine is "in an infinite loop" if its
computation repeats a configuration (and hence doesn't halt).

If a TM M is guaranteed to either halt or go into an infinite
loop on string w, then it is possible to decide which happens
(i.e., we don't care what our decider does if the above condition
isn't met).  Simply have the deciding machine simulate machine M's
computation on w, recording all configurations and checking for
a repetition.  Either M will halt, or a repetition will be found.
Therefore the decider will be able to halt with a yes or no answer.

On the other hand, given a TM M and a string w, it is not possible
to decide yes if M goes into an infinite loop on w and no otherwise.
If this were possible, we could decide the halting problem.  We want
to decide, given a machine M and string w, if M halts on w.  Modify
M to get M', a machine which computes as M does with the exception
that where M halts, M' goes into a loop (10: goto 10).  Now decide
if M' has an infinite loop on w.  If it doesn't, we know M doesn't
halt on w so we say no.  If it does, we know that M either halts
or goes into an infinite loop some other way.  However, from above
we can decide which is the case.  Therefore we can decide whether
M halts on w, given the ability to decide if a machine goes into
an infinite loop on a string.  We have a contradiction, so the
problem of deciding if a machine goes into an infinite loop must
be undecidable.

Rich
-- 

	"a picture in the head is a gory murder in an art gallery"

					-- Stephen Kosslyn