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!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!decwrl!glacier!kestrel!ladkin
From: ladkin@kestrel.ARPA
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem: a meaty response
Message-ID: <4374@kestrel.ARPA>
Date: Wed, 29-Jan-86 15:31:29 EST
Article-I.D.: kestrel.4374
Posted: Wed Jan 29 15:31:29 1986
Date-Received: Sat, 1-Feb-86 02:04:32 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> <1070@mmintl.UUCP>
Distribution: net
Organization: Kestrel Institute, Palo Alto, CA
Lines: 41
Xref: watmath net.ai:3238 net.philosophy:4003

(wiener)
> >There are problems now known which are believed forever insoluble.
> 
(adams)
> There does not seem to be any way to know that a problem
> is definitely insoluble (as distinct from undecidable in a formal system).

There are theorems such as Kruskal's, the Paris-Harrington
version of the Ramsey Theorem, and Friedman's various principles
that are provable stronger than the generally acceptable
principles of arithmetic, and recursive set theory. They are
arguably consistent, since there are `proofs' of them. 
These proofs must depend upon stronger principles than all
mathematicians are willing to accept (e.g. intuitionists).
If you believe these proofs, you will nevertheless be
unable to persuade those who are sceptical of their validity,
and furthermore, there is a proof of this fact.

This point is even valid for Peano Arithmetic.
If you believe that Peano Arithmetic is consistent, as I do,
then there is a proof that proving the consistency of P.A.
from elementary principles is an insoluble problem. 
This is different from deciding the 
consistency of P.A. If you believe Gentzen's proof, as I do,
then the consistency is already decided.

The conclusion I suggest is that:
 Given the FACT that a mathematical principle is undecided by
some formal system, then you would conclude that the consistency
of the principle is an unsolvable problem 
IF EITHER 
you see reason to doubt the principle, but believe it 
consistent nevertheless,
OR 
if you believe the principle.

Hence whether a problem is provably insoluble depends upon the
entirety of the mathematical principles you are willing to accept
as valid.

Peter Ladkin