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!burl!ulysses!bellcore!decvax!decwrl!glacier!kestrel!ttp
From: ttp@kestrel.ARPA
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <3978@kestrel.ARPA>
Date: Thu, 16-Jan-86 02:38:37 EST
Article-I.D.: kestrel.3978
Posted: Thu Jan 16 02:38:37 1986
Date-Received: Sat, 18-Jan-86 07:19:10 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP>
Distribution: net
Organization: Kestrel Institute, Palo Alto, CA
Lines: 29
Xref: watmath net.ai:3181 net.philosophy:3800
Summary: is there an unsolvable problem?

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.

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

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?

-tom