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!cbosgd!ihnp4!houxm!vax135!cornell!uw-beaver!tektronix!hplabs!pesnta!pyramid!decwrl!decvax!genrad!panda!talcott!harvard!cmcl2!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <1056@mmintl.UUCP>
Date: Sat, 18-Jan-86 15:04:08 EST
Article-I.D.: mmintl.1056
Posted: Sat Jan 18 15:04:08 1986
Date-Received: Thu, 23-Jan-86 08:50:45 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Distribution: net
Organization: Multimate International, E. Hartford, CT
Lines: 52
Xref: watmath net.ai:3200 net.philosophy:3879
Summary: A negative response


In article <3978@kestrel.ARPA> ttp@kestrel.ARPA writes:
>The question of whether or not people are capable of solving the
>Halting problem in general (which, as people have abundantly shown, is
>equivalent to solving your favorite outstanding mathematical problem)
>does not seem amenable to a rational answer. Sure there are hard
>problems, but cleverer people pop up over the centuries and solve some
>of the outstanding problems, but then the remaining problems are
>harder, etc.  I suspect that I at least am not capable of solving
>every problem (such humility).
>
>The REAL question for me is whether the following is correct reasoning:
>
>Premise 1: No Turing machine will solve the Halting problem for every
>input.
>
>Premise 2:  The human "race" is equivalent (in problem solving power)
>to a Turing machine.
>
>Consequent (?): There is some PARTICULAR input for which the human
>race can never solve the Halting problem.

This consequent does follow from the premises.  Also, premise 1 has been
proved mathematically.

>If so, and one believes premise 2, can we construct such an unsolvable
>problem, in finite time, and then get on with life?

No.  Any Turing machine which is reasonably good at solving the halting
problem will eventually get a positive answer for any input which does
halt -- simply by running the algorithm (interspersed with other work)
until it halts.  So if we can show such a Turing machine fails to solve
the halting problem for an input, we know the input does not halt.  But
we are perfectly capable of realizing this about ourselves.  The conclusion
is that we can never know for sure about any problem that we cannot solve
it.

To look at this from a different angle, given a Turing machine, one can
construct an input to the halting problem which that Turing machine cannot
answer correctly (it may answer it incorrectly, or it may fail to answer).
However, to do this, we need to know exactly what the Turing machine is.
But we manifestly cannot fully specify a Turing machine which is equivalent
to the computational abilities of the entire human race.

>Currently we have an ineffective algorithm for finding the unsolvable
>problem, should it exist, namely: work on problems, and if no one ever
>solves one, then that one is unsolvable. But can we find out before
>forever?

No.

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