home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1B / DATAFILE_PDCD1B.iso / _gutenburg / gutenberg / ippe / chaitin_tx / CHAITIN_TX
Text File  |  1994-03-01  |  57KB  |  2,044 lines
  1.  
  2. RANDOMNESS & COMPLEXITY IN PURE MATHEMATICS
  3.  
  4.  
  5.  
  6. _International Journal of Bifurcation and Chaos_, 
  7. Vol. 4, No. 1, February 1994
  8.  
  9.  
  10.  
  11.  
  12. G.J. Chaitin
  13. IBM Research Division
  14. P.O. Box 704
  15. Yorktown Heights, NY
  16. 10598, USA
  17. <chaitin@watson.ibm.com>
  18.  
  19.  
  20.  
  21. Abstract
  22.  
  23.  
  24. One normally thinks that everything that is true is true for a reason.
  25.  
  26. I've found mathematical truths that are true for no reason at all. These
  27. __________________________ 
  28. 1Lecture given Thursday 22 October 1992 at a Mathematics - Computer Science
  29. Colloquium at the University of New Mexico. The lecture was videotaped;
  30. this is an edited transcript. Originally published under the title
  31. "Randomness in arithmetic and the decline and fall of reductionism in
  32. pure mathematics" in the June 1993 issue of the Bulletin of the European
  33. Association for Theoretical Computer Science.
  34.  
  35.  
  36.  
  37.                                 1
  38.  
  39.  
  40.  
  41.  
  42. 2
  43.  
  44.  
  45.  
  46. mathematical truths are beyond the power of mathematical reasoning
  47.  
  48. because they are accidental and random.
  49.  
  50.    Using  software  written  in  Mathematica  that  runs  on  an  IBM
  51.  
  52. RS/6000 workstation, I constructed a perverse 200-page algebraic e-
  53.  
  54. quation with a parameter N and 17,000 unknowns:
  55.  
  56.             Left-Hand-Side(N) = Right-Hand-Side(N).
  57.  
  58. For each whole-number value of the parameter N, ask whether this
  59.  
  60. equation has a finite or an infinite number of whole number solutions.
  61.  
  62. The answers escape the power of mathematical reason because they are
  63.  
  64. completely random and accidental.
  65.  
  66.    This work is an extension of famous results of G"odel and Turing
  67.  
  68. using ideas from a new field called algorithmic information theory.
  69.  
  70.  
  71.  
  72. 1.  Hilbert on the axiomatic method
  73.  
  74.  
  75. Last month I was a speaker at a symposium on reductionism at Cam-
  76.  
  77. bridge University where Turing did his work. I'd like to repeat the talk
  78.  
  79. I gave there and explain how my work continues and extends Turing's.
  80.  
  81. Two previous speakers had said bad things about David Hilbert. So I
  82.  
  83. started by saying that in spite of what you might have heard in some
  84.  
  85. of the previous lectures, Hilbert was not a twit!
  86.  
  87.    Hilbert's idea is the culmination of two thousand years of math-
  88.  
  89. ematical tradition going back to Euclid's axiomatic treatment of ge-
  90.  
  91. ometry, going back to Leibniz's dream of a symbolic logic and Russell
  92.  
  93. and Whitehead's monumental Principia Mathematica. Hilbert's dream
  94.  
  95. was to once and for all clarify the methods of mathematical reasoning.
  96.  
  97. Hilbert wanted to formulate a formal axiomatic system which would
  98.  
  99. encompass all of mathematics.
  100.  
  101.                    Formal Axiomatic System
  102.  
  103.                    --------->
  104.  
  105.                    --------->
  106.  
  107.                    --------->
  108.  
  109.    Hilbert emphasized a number of key properties that such a formal
  110.  
  111. axiomatic system should have. It's like a computer programming lan-
  112.  
  113. guage.  It's a precise statement about the methods of reasoning, the
  114.  
  115.  
  116.  
  117.  
  118. Randomness & Complexity in Pure Mathematics                  3
  119.  
  120.  
  121.  
  122. postulates and the methods of inference that we accept as mathemati-
  123.  
  124. cians. Furthermore Hilbert stipulated that the formal axiomatic system
  125.  
  126. encompassing all of mathematics that he wanted to construct should
  127.  
  128. be "consistent" and it should be "complete."
  129.  
  130.  
  131.                   Formal Axiomatic System
  132.  
  133.                   ---------> consistent
  134.  
  135.                   ---------> complete
  136.  
  137.                   --------->
  138.  
  139.  
  140.     Consistent means that you shouldn't be able to prove an assertion
  141.  
  142. and the contrary of the assertion.
  143.  
  144.  
  145.                   Formal Axiomatic System
  146.  
  147.                   ---------> consistent A ~A
  148.  
  149.                   ---------> complete
  150.  
  151.                   --------->
  152.  
  153.  
  154. You shouldn't be able to prove A and ~A (not A).  That would be very
  155.  
  156. embarrassing.
  157.  
  158.     Complete means that if you make a meaningful assertion you should
  159.  
  160. be able to settle it one way or the other. It means that either A or not
  161.  
  162. A should be a theorem, should be provable from the axioms using the
  163.  
  164. rules of inference in the formal axiomatic system.
  165.  
  166.  
  167.                   Formal Axiomatic System
  168.  
  169.                   ---------> consistent A ~A
  170.  
  171.                   ---------> complete A ~A
  172.  
  173.                   --------->
  174.  
  175.  
  176. Consider a meaningful assertion A and its contrary not A.  Exactly
  177.  
  178. one of the two should be provable if the formal axiomatic system is
  179.  
  180. consistent and complete.
  181.  
  182.     A formal axiomatic system is like a programming language. There's
  183.  
  184. an alphabet and rules of grammar, in other words, a formal syntax. It's
  185.  
  186. a kind of thing that we are familiar with now.  Look back at Russell
  187.  
  188. and Whitehead's three enormous volumes full of symbols and you'll feel
  189.  
  190. you're looking at a large computer program in some incomprehensible
  191.  
  192. programming language.
  193.  
  194.  
  195.  
  196.  
  197. 4
  198.  
  199.  
  200.  
  201.    Now there's a very surprising fact. Consistent and complete means
  202.  
  203. only truth and all the truth. They seem like reasonable requirements.
  204.  
  205. There's a funny consequence, though, having to do with something
  206.  
  207. called the decision problem. In German it's the Entscheidungsproblem.
  208.  
  209.  
  210.                   Formal Axiomatic System
  211.  
  212.                   ---------> consistent A ~A
  213.  
  214.                   ---------> complete A ~A
  215.  
  216.                   ---------> decision problem
  217.  
  218.  
  219.    Hilbert ascribed a great deal of importance to the decision problem.
  220.  
  221.  
  222.                   HILBERT
  223.  
  224.                   Formal Axiomatic System
  225.  
  226.                   ---------> consistent A ~A
  227.  
  228.                   ---------> complete A ~A
  229.  
  230.                   ---------> decision problem
  231.  
  232.  
  233.    Solving the decision problem for a formal axiomatic system is giving
  234.  
  235. an algorithm that enables you to decide whether any given meaningful
  236.  
  237. assertion is a theorem or not.  A solution of the decision problem is
  238.  
  239. called a decision procedure.
  240.  
  241.  
  242.                   HILBERT
  243.  
  244.                   Formal Axiomatic System
  245.  
  246.                   ---------> consistent A ~A
  247.  
  248.                   ---------> complete A ~A
  249.  
  250.                   ---------> decision procedure
  251.  
  252.  
  253.    This sounds weird. The formal axiomatic system that Hilbert wanted
  254.  
  255. to construct would have included all of mathematics:  elementary
  256.  
  257. arithmetic, calculus, algebra, everything.  If there's a decision proce-
  258.  
  259. dure, then mathematicians are out of work. This algorithm, this
  260.  
  261. mechanical procedure, can check whether something is a theorem or not,
  262.  
  263. can check whether it's true or not. So to require that there be a decision
  264.  
  265. procedure for this formal axiomatic system sounds like you're asking
  266.  
  267. for a lot.
  268.  
  269.    However it's very easy to see that if it's consistent and it's complete
  270.  
  271. that implies that there must be a decision procedure. Here's how you do
  272.  
  273.  
  274.  
  275.  
  276. Randomness & Complexity in Pure Mathematics                  5
  277.  
  278.  
  279.  
  280. it. You have a formal language with a finite alphabet and a grammar.
  281.  
  282. And Hilbert emphasized that the whole point of a formal axiomatic sys-
  283.  
  284. tem is that there must be a mechanical procedure for checking whether
  285.  
  286. a purported proof is correct or not, whether it obeys the rules or not.
  287.  
  288. That's the notion that mathematical truth should be objective so that
  289.  
  290. everyone can agree whether a proof follows the rules or not.
  291.  
  292.     So if that's the case you run through all possible proofs in size order,
  293.  
  294. and look at all sequences of symbols from the alphabet one character
  295.  
  296. long, two, three, four, a thousand, a thousand and one. . .a hundred
  297.  
  298. thousand characters long. You apply the mechanical procedure which
  299.  
  300. is the essence of the formal axiomatic system, to check whether each
  301.  
  302. proof is valid.  Most of the time, of course, it'll be nonsense, it'll be
  303.  
  304. ungrammatical.  But you'll eventually find every possible proof.  It's
  305.  
  306. like a million monkeys typing away.  You'll find every possible proof,
  307.  
  308. though only in principle of course.  The number grows exponentially
  309.  
  310. and this is something that you couldn't do in practice. You'd never get
  311.  
  312. to proofs that are one page long.
  313.  
  314.     But in principle you could run through all possible proofs, check
  315.  
  316. which ones are valid, see what they prove, and that way you can sys-
  317.  
  318. tematically find all theorems.  In other words, there is an algorithm,
  319.  
  320. a mechanical procedure, for generating one by one every theorem that
  321.  
  322. can be demonstrated in a formal axiomatic system.  So if for every
  323.  
  324. meaningful assertion within the system, either the assertion is a the-
  325.  
  326. orem or its contrary i