[FOM] Experimentation, Incompleteness, and Undecidability
Dmytro Taranovsky
dmytro at mit.edu
Wed Feb 11 22:33:41 EST 2004
Timothy Chow writes:
|Suppose that you encounter a machine that allegedly solves the halting
|problem. You ask the computer, "Would a machine that blindly searches
|for a proof of a contradiction from the axioms `ZFC + [some humongous
|cardinal] exists' halt?" The computer prints out, "No." How should
you
|interpret this incident?
|(a) The computer's answer increases your confidence in the consistency
|of "ZFC + humongous cardinal" by directly computing the answer for you.
|(b) The incident is an experimental test of the physical theory that
| led to the prediction that the computer is indeed a "hypercomputer,"
| and your a priori confidence in the consistency of "ZFC + humongous
| cardinal" increases your confidence in the correctness of the
| physical theory.
|(c) Neither a nor b; you have gained no information about large
| cardinals or about the possibility of hypercomputation.
The answer is both (a) and (b) because the result connects two seemingly
unrelated fields. Suppose, for example, that a priori philosophical and
mathematical evidence gives a 90% probability of consistency of
humongous cardinal (whatever it is); that before the experiment the
probability that the theory is true is 89%; that the probability that
the experiment (as interpreted by the theory) will yield the correct
mathematical result is 99% if the theory is true but 50% otherwise; and
that before the experiment the reasons for believing consistency of
humongous cardinals are independent from the reasons for believing the
theory.
Then, an application of the laws of probability gives: ZFC+there is a
humongous cardinal is consistent with probability p = (probability
before the experiment that the results are as observed and ZFC+there a
humongous cardinal is consistent)/(probability before the experiment
that the results are as observed) = (0.9*(0.89*0.99+(1-0.89)*0.50))/
(0.9*(0.89*0.99+(1-0.89)*0.50)+(1-0.9)*(0.89*(1-0.99)+(1-0.89)*(1-0.50))) =0.84249/0.84888 = (approximately) 99.2%, and the theory is correct with probability (0.89*(0.9*0.99+(1-0.9)*(1-0.99)))/0.84888= 0.79388/0.84888 = (approximately) 93.5%.
Thus, the experiment confirms both the physical theory and the
mathematical hypothesis. When the physical theory is still speculative,
the experimental results based on questions to which we know the answer
(like consistency of PA or inconsistency of PA with the negation of
Fermat's theorem) would serve primarily to confirm the theory, but when
the theory becomes established, the results would (with high
probability) resolve unsolved mathematical questions.
A similar phenomenon occurs in mathematics when there is a proof of an
equivalence or a deep interrelationship between hypotheses in different
fields. For example, the equivalence between nonexistence of nontrivial
zeroes of zeta function off the line {s: Re(s)=1/2} and a statement
about distribution of primes (pi(n)=Li(n)+O(Sqrt(x)*ln x)) gives
plausibility to the Riemann hypothesis. The relationship between large
cardinals and determinacy hypotheses provides evidence for both.
It is unlikely that such an experiment will be successfully conducted
any time soon. However, undecidability and incompleteness can surface
in other ways. For a number of important physical theories, consistency
has not been proved. For example (correct me if I am wrong), the
mathematical consistency of quantum electrodynamics (QED) is still an
open question, even though some of its predictions are confirmed to 11
decimal digits. Conceivably, QED is consistent, but its consistency
entails consistency of some large cardinal axioms.
However, a much more likely scenario is that currently accepted physical
theories combined with say Con(ZFC+Projective Determinacy) lead to a
certain prediction that will be confirmed by an experiment. The
physical theories with just ZFC would also lead to the same prediction,
but would require prohibitively complicated calculations to arrive at
the prediction. Although I am rather confident that such predictions
exist, I am not aware of any specific experiment to that effect; perhaps
Harvey Friedman knows better.
Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm
More information about the FOM
mailing list