Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 alpha 4/15/85; site kestrel.ARPA
Path: utzoo!watmath!clyde!cbosgd!ukma!psuvm.bitnet!psuvax1!burdvax!sdcrdcf!hplabs!pesnta!pyramid!decwrl!glacier!kestrel!ladkin
From: ladkin@kestrel.ARPA
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <4130@kestrel.ARPA>
Date: Tue, 21-Jan-86 16:48:46 EST
Article-I.D.: kestrel.4130
Posted: Tue Jan 21 16:48:46 1986
Date-Received: Thu, 23-Jan-86 10:53:16 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> <633@harvard.UUCP>
Distribution: net
Organization: Kestrel Institute, Palo Alto, CA
Lines: 42
Xref: watmath net.ai:3204 net.philosophy:3899

In article <633@harvard.UUCP>, draves@harvard.UUCP (Richard Draves) writes:
> 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). [........]
> 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.
> [......]

An interesting question :-
 Is there an algorithm which, given a program P written in your
favorite procedural language (with or without recursion), will
produce a Turing machine M-sub-P, and an input translator T-sub-P
(if P accepts input) such that M-sub-P halts on T-sub-P(I) iff
P halts on I, for all inputs I, and, additionally, if P goes
into an (informal) infinite loop on I, then
M-sub-P goes into a repeated-configuration infinite loop,
as defined above, on T-sub-P(I)?

It follows from the results above that, if there is such an
algorithm, it is decidable whether a program written in your
favorite procedural language has an (informal) infinite loop.

I'm interested in the question because there are programs
such as
         n = 1;
         while n > 0 do
                       begin write(n);
                             increment n;
                       end
which are in an infinite loop (by the usual informal account),
but for which no configuration repeats (a configuration would
be in this case the values of n and the program counter).

I suspect someone knows the answer already.

Peter Ladkin
ladkin@kestrel