Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site boring.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!mcvax!boring!lambert
From: lambert@boring.UUCP
Newsgroups: net.math
Subject: Re: Undecidability and Proof
Message-ID: <6650@boring.UUCP>
Date: Sat, 12-Oct-85 10:30:45 EDT
Article-I.D.: boring.6650
Posted: Sat Oct 12 10:30:45 1985
Date-Received: Tue, 15-Oct-85 04:48:52 EDT
References: <106@milford.UUCP>
Reply-To: lambert@boring.UUCP (Lambert Meertens)
Organization: CWI, Amsterdam
Lines: 38
Apparently-To: rnews@mcvax.LOCAL

> "... if you succeeded in proving that Fermat's problem is unsolvable, 
> then ipso facto you would have shown that the conjecture is true.
> Because if there was a counterexample, then with some big computer,
> some day someone would pull out the counterexample."
> 
> How common is this attitude toward undecidability questions?
> [...]
> Has anyone else encountered this type of argument? How do people
> feel about this type of 'proof'? Also, what is the attitude toward
> such a Platonic notion of ideal "Truth"?

The argument may be given much more precisely.  A problem is that the
notion of "(recursive) solvability" or "decidability" is defined only for a
*class* of problems, not for a specific instance. However, if we let "P"
stand for some specific problem, then we can consider P' = "P & n=n", and
ask for an algorithm that, given an input value n0 for n, will output 0 or
1 if P'-with-n-replaced-by-n0 is false or true, respectively.  Such an
algorithm, if it exists, is insensitive to its input.

There is a Platonic proof that no specific problem P (generalized in the
above way) is unsolvable. The argument is: either P is false, or it is
true. If it is false, the algorithm "Output 0" solves the problem;
otherwise, "Output 1" does. This argumentation is unacceptable to
intuitionists and constructivists (although they would accept the
conclusion!).

For problems like F = "Fernat was right", that can be refuted by a
counterexample, there is much better argument.  Clearly, if there exists a
counterexample to F, then F is false. So, in that case, the algorithm
"Output 0" solves F', so there exists an algorithm for solving F'.  If
someone succeeds in proving that F' is unsolvable, such an algorithm cannot
exist, so it follows that no counterexample to F exists. The latter is
equivalent to "F is true".
-- 

     Lambert Meertens
     ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP
     CWI (Centre for Mathematics and Computer Science), Amsterdam