Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site mmintl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!linus!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <1063@mmintl.UUCP>
Date: Tue, 21-Jan-86 03:50:20 EST
Article-I.D.: mmintl.1063
Posted: Tue Jan 21 03:50:20 1986
Date-Received: Fri, 24-Jan-86 21:24:28 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> <436@faron.UUCP> <4024@kestrel.ARPA>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Distribution: net
Organization: Multimate International, E. Hartford, CT
Lines: 46
Xref: watmath net.ai:3206 net.philosophy:3906

In article <4024@kestrel.ARPA> ladkin@kestrel.ARPA writes:
>In article <436@faron.UUCP>, bs@faron.UUCP (Robert D. Silverman) writes:
>> One interesting aspect of
>> the whole business is the fact that we can never know when in fact a problem
>> is undecidable. 
>
>False. There are many sets which are recursively enumerable but not
>recursive. This means that membership in such a set is undecidable
>in general. The set of all theorems of first-order logic is such a
>set (provided there is at least one non-monadic predicate in the 
>language).

This argument hinges on a linguistic point: what is a problem?  If a problem
is a single question, then the original statement is correct.  For a set of
problems, there may be no procedure which produces answers to all of the
problems.  Restating this as a single problem, the question is "what is
the procedure for finding answers to questions in this set?"; and the
answer is "there is no such procedure".

It is true that we can never know when in fact a particular problem is
insolvable by us.

>No argument has been provided in this discussion for the undcidability
>of the detection of infinite loops, as a special case of 
>non-termination.

Again, we have a semantic question.  I think most posters on this subject
are using "infinite loop" as a synonym for "non-terminating computation".

If by "infinite loop" you mean "repeats the same set of machine states",
then detecting infinite loops is like detecting halting.  One can readily
build a Turing machine which will analyze another Turing machine with input,
and "return" true if the machine goes into an infinite loop, false if it
halts, and fail to halt if it performs any other kind of unterminating
computation.

Conversely, given a Turing machine which attempts to solve an interesting
mathematical problem, and halts if it finds a solution, one can add an
addition state or two to the machine, which causes a simple infinite loop
when one of those states is entered, and have a machine which goes into
an "infinite loop" if an only if the original machine halted (one must
be able to guarantee that the original never went into an infinite loop,
but this is easy for this kind of example).

Frank Adams                           ihpn4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108