Information-Theoretic Limitations of Formal Systems

ABSTRACT

An attempt is made to apply information-theoretic computational complexity to meta-mathematics. The paper studies the number of bits of instructions that must be given to a computer for it to perform finite and infinite tasks, and also the time it takes the computer to perform these tasks. This is applied to measuring the difficulty of proving a given set of theorems, in terms of the number of bits of axioms that are assumed, and the size of the proofs needed to deduce the theorems from the axioms.

REFERENCES

• 1: CHAITIN, G.J. Information-theoretic aspects of Post's construction of a simple set. On the difficulty of generating all binary strings of complexity less than n. (Abstracts.) AMS Notices 19 (1972), pp. A-712, A-764.
• 2: CHAITIN, G.J. On the greatest natural number of definitional or information complexity __<n. There are few minimal descriptions. (Abstracts.) Recursive Function Theory: Newsletter, no. 4 (1973), pp. 11-14, Dep. of Math., U. of California, Berkeley.
• 3: vos NEUMANN, J. Method in the physical sciences. J. yon Neumann--Collecfed Works, Vol. VI, A. H. Taub, Ed., MacMillan, New York, 1963, No. 36, pp. 491-498.
• 4: yon NEU~ANN, J. The mathematician. In The World of Mathematics, Vol. }~, J. R. Newman, Ed., Simon and Schuster, New York, 1956, pp. 2053-2063.
• 5: BELL, E. T. Mathematics: Queen and Servant of Science. McGraw-Hill, New York, 1951, pp. 414-415.
• 6: WEYL, H. Mathematics and logic. Amer. Math. Mon. 53 (1946), 1-13.
• 7: WEYL, H. Philosophy of Mathematics and Natural Science. Princeton U. Press, Princeton, N.J., 1949, pp. 234-235.
• 8: TURINO, A.M. Solvable and unsolvable problems. In Science News, no. 31 (1954), A. W. Heaslett, Ed., Penguin Books, Harmondsworth, Middlesex, England, pp. 7-23.
• 9: NAGEL, E., AND NEWMAN, J.R. GOdel's Proof. Routledge & Kegan Paul, London, 1959.
• 10: DAVIS, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
• 11: QUINE, W.V. Paradox. Scientific American 206, 4 (April 1962), 84-96.
• 12: KLEENE, S.C. Mathematical Logic. Wiley, New York, 1968, Ch. V, pp. 223-282.
• 13: GODEL, K. On the length of proofs. In The Undecidable, M. Davis, Ed., ~aven Press, Hewlett. N.Y., 1965, pp. 82-83.
• 14: COHEN, P.J. Set Theory and the Continuum Hypothesis. Benjamin, New York, 1966, p. 45.
• 15: ARmB, M. A. Speed-up theorems and incompleteness theorems. In Automata Theory, E. R. Cainiello, Ed., Academic Press, New York, 1966, pp. 6-24.
• 16: EHRENFEUCHT, A., AND MYCIELSKI, J. Abbreviating proofs by adding new axioms. AMS Bull. 77 (1971), 366-367.
• 17: P6LVA, G. Heuristic reasoning in the theory of numbers. Amer. Math. Mon. 66 (1959), 375-384.
• 18: EINSTEIN, A. Remarks on Bertrand Russell's theory of knowledge. In The Philosophy of Bertrand Russell, P. A. Schilpp, Ed., Northwestern U., Evanston, Ill., 1944, pp. 277-291.
• 19: HAWKINS, D. Mathematical sieves. Scientific American 199, 6 (Dec. 1958), 105-112.
• 20: KOLMOGOROV, A.N. Logical basis for information theory and probability theory. IEEE Trans. IT-I$ (1968), 662-664.
• 21: MARTZN-LiSF, P. Algorithms and randomness. Rev. oflnternat. Statist. Inst. 37 (1969), 265-272.
• 22: LOVELAND, D.W. A variant of the Kolmogorov concept of complexity. Inform. and Contr. 15 (1969), 510-526.
• 23: CHAITIN, G.j. On the difficulty of computations. IEEE Trans. IT-16 (1970),5-9.
• 24: David G. Willis, Computational Complexity and Probability Constructions, Journal of the ACM (JACM), v.17 n.2, p.241-259, April 1970 [doi>10.1145/321574.321578]
• 25: ZVONKIN, A. I~., AND LEVIN, L.A. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Math. Surveys 25, 6 (Nov.-Dec. 1970), 83-124.
• 26: SCHNORR, C.P. ZufdUigkeit und Wahrscheinlichkeit~Eine algorithmische Begrfindung der Wahrscheinlichkeitstheorie. Springer, Berlin, 1971.
• 27: FINE, T.L. Theories of Probability~An Examination of Foundations. Academic Press, New York, 1973.
• 28: CHAITIS, G.J. Information-theoretic computational complexity. IEEE Trans. IT-SO (1974), 10-15.
• 29: DELONG, H. A Profile of Mathematical Logic. Addison-Wesley, Reading, Mass., 1970, Sec. 28.2, pp. 208-209.
• 30: DAws, M. Hilbert's tenth problem is unsolvable. Amer. Math. Mon. 80 (1973), 233-269.
• 31: POST, E. Recursively enumerable sets of positive integers and their decision problems. In The Undecidable, M. Davis, Ed., Raven Press, Hewlett, N.Y., 1965, pp. 305--337.
• 32: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 33: SHOENFIELV, J.R. Mathematical Logic. Addison-Wesley, Reading, Mass., 1967, See. 1.2, pp. 2-20.
• 34: Elliott Mendelson, Introduction to mathematical logic (3rd ed.), Wadsworth Publ. Co., Belmont, CA, 1987
• 35: RlssELI~, B. Mathematical logic as based on the theory of types. In From Frege to Gsdel, J. van Heijenoort, Ed., Harvard U. Press, Cambridge, Mass., 1967, pp. 150-182.
• 36: Shen Lin , Tibor Rado, Computer Studies of Turing Machine Problems, Journal of the ACM (JACM), v.12 n.2, p.196-212, April 1965 [doi>10.1145/321264.321270]
• 37: D. W. Loveland, On minimal-program complexity measures, Proceedings of the first annual ACM symposium on Theory of computing, p.61-78, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805422]
• 38: RoQm~s, H. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
• 39: G~vwL, K. What is Cantor's continuum problem? In Philosophy of Ma~hemaLics, Benacerraf, P., and Putnam, H., Eds., Prentice-Hall, Englewood Cliffs, N.J., 1964, pp. 258-273.
• 40: SCHWARTZ, J.T. A short survey of computational complexity theory. Notes, Courant Institute of Mathematical Sciences, NYU, New York, 1972.
• 41: ScHw~tRrz, J.T. On Programrain~: An Interim Report on the SETL PrOject. In~tallmen~ 1: Generalities, Lecture Notes, Courant Institute of Mathematical Sciences, NYU, New York, 1973.
• 42: CKaITIN, G.J. A theory of program size formally identical to information theory. Res. Rep. RC4805, IBM Res. Center, Yorktown Heights, N.Y., 1974.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Performance, Theory, Verification