Information-Theoretic Incompleteness

The following sections are included:

• Foreword

• Contents

The following sections are included:

• Beginnings

• Adult Activities

We review the Turing machine version of a fundamental information-theoretic incompleteness theorem, which asserts that it is difficult to prove that specific strings s have high Turing machine state complexity H_tm(s). We also construct a Thing machine “halting probability” Ω_tm with the property that the initial segments of its base-two expansion asymptotically have the maximum possible Turing machine complexity H_tm.

We review four different versions of the information-theoretic incompleteness theorem asserting that it is difficult to prove that specific strings s have high blank-endmarker complexity H_b(s). We also construct a blank-endmarker “halting probability” Ω_b with the property that the initial segments of its base-two expansion asymptotically have the maximum possible blank-endmarker complexity H_b.

A theory of program-size complexity for something close to real LISP is sketched.

We present the information-theoretic incompleteness theorems that arise in a theory of program-size complexity based on something close to real LISP. The complexity of a formal axiomatic system is defined to be the minimum size in characters of a LISP definition of the proof-checking function associated with the formal system. Using this concrete and easy to understand definition, we show (a) that it is difficult to exhibit complex S-expressions, and (b) that it is difficult to determine the bits of the LISP halting probability Ω_LISP. We also construct improved versions Ω^′_LISP and Ω^″_LISP of the LISP halting probability that asymptotically have maximum possible LISP complexity.

We present a “parenthesis-free” dialect of LISP, in which (a) each primitive function has a fixed number of arguments, and (b) the parentheses associating a primitive function with its arguments are implicit and are omitted. The parenthesis-free complexity of an S-expression e is defined to be the minimum size in characters ∣p∣ of a parenthesis-free LISP expression p that has the value e. We develop a theory of program-size complexity for parenthesis-free LISP by showing (a) that the maximum possible parenthesis-free complexity of an n-bit string is ∼ βn, and (b) how to construct three parenthesis-free LISP halting probabilities Ω_pf, Ω^′_pf and Ω^″_pf.

We present a new “character-string” oriented dialect of LISP in which the natural LISP halting probability asymptotically has maximum possible LISP complexity.

We propose an improved definition of the complexity of a formal axiomatic system: this is now taken to be the minimum size of a self-delimiting program for enumerating the set of theorems of the formal system. Using this new definition, we show (a) that no formal system of complexity n can exhibit a specific object with complexity greater than n + c, and (b) that a formal system of complexity n can determine at most n + c scattered bits of the halting probability Ω. We also present a short, self-contained proof of (b).

Please refer to full text.

God not only plays dice in physics but also in pure mathematics. Mathematical truth is sometimes nothing more than a perfect coin toss.

Lecture given Tuesday 15 January 1991 in the Technical University of Vienna, at a meeting on “Mathematik und Weltbild,” immediately following a lecture by Prof. Hans-Christian Reichel on “Mathematik und Weltbild seit Kurt Gödel.” The lecture was videotaped; this is an edited transcript.

The following sections are included:

• History

• How to toss a coin?

• Information theory

• Undecidability of halting problem (Turing 1936)

• The halting probability Ω

• “Computing” Ω in the limit

• Equation for Ω

• Solvable/unsolvable?

• Finitely/infinitely many solutions?

• Universal diophantine equation

• Constructing the equation

• Toy pure LISP

• LISP register machine

• Summary

• References

Les mathématiques passent pour l'incarnation de la rigueur logique et de l'exactitude. Peut-on néanmoins y déceler du désordre ? Dans les années 1930, les travaux du logicien Kurt Gödel, en démontrant l'≪ incomplétude ≫ des mathéinatiques, avaient déjà ébranlé quelques solides certitudes. Plus récemment, G. J. Chaitin a proposé une définition du hasard faisant appel à la théorie algorithmique de l'information. Moyennant cette définition, l'auteur a pu montrer que certaines questions en théorie des nombres ont des réponses tout aussi aléatoires que le résultat d'un jeu de pile ou face. Les mathématiques joueraient-elles donc aux dés ?

I have developed a mathematical theory of complexity, which I call “algorithmic information theory.” I have applied this theory to mathematics itself, and have shown that mathematics is not as simple as had been thought, and indeed that arithmetic contains infinite complexity and complete randomness. Here I shall give examples of my mathematical concept of complexity and how it is measured, outline its main properties, and discuss what it says about the limitations of mathematics.

This remarkable quotation comes from Rényi's unfinished 1969 manuscript, written in the form of a fictitious student's diary. This “diary” comprises the bulk of Rényi's posthumous work, A Diary on Information Theory, a stimulating introduction to information theory and an essay on the mathematical notion of information, a work left incomplete at Rényi's death in 1970 at the age of 49.

The following sections are included:

• Epilogue The Challenge for the Future
  • COMPLEXITY AND BIOLOGY
  • AFTERWORD

• Bibliography
  • SOURCES OF QUOTATIONS
  • CLASSICS

• About the author