Издательство World Scientific, 1997, -534 pp.
God not only plays dice in quantum mechanics, but even with the whole numbers! The discovery of randomness in arithmetic is presented in my book Algorithmic Information Theory published by Cambridge University Press. There I show that to decide if an algebraic equation in integers has finitely or infinitely many solutions is in some cases absolutely intractable. I exhibit an infinite series of such arithmetical assertions that are random arithmetical facts, and for which it is essentially the case that the only way to prove them is to assume them as axioms. This extreme form of G?del incompleteness theorem shows that some arithmetical truths are totally impervious to reasoning.
The papers leading to this result were published over a period of more than twenty years in widely scattered jouals, but because of their unity of purpose they fall together naturally into the present book, intended as a companion volume to my Cambridge University Press monograph. I hope that it will serve as a stimulus for work on complexity, randomness and unpredictability, in physics and biology as well as in metamathematics.
For the second edition, I have added the article Randomness in arithmetic (Part I), a collection of abstracts (Part VII), a bibliography (Part VIII), and, as an Epilogue, two essays which have not been published elsewhere that assess the impact of algorithmic information theory on mathematics and biology, respectively. I should also like to point out that it is straightforward to apply to LISP the techniques used in Part VI to study bounded-transfer Turing machines. A few footnotes have been added to Part VI, but the subject richly deserves book length treatment, and I intend to write a book about LISP in the near future.
I Introductory/Tutorial/Survey/Papers
Randomness and mathematical proof
Randomness in arithmetic
On the difficulty of computations
Information-theoretic computational complexity
Algorithmic information theory
Algorithmic information theory
II Applications to Metamathematics
G?del’s theorem and information
Randomness and G?del’s theorem
An algebraic equation for the halting probability
Computing the busy beaver function
III Applications to Biology
To a mathematical definition of life
Toward a mathematical definition of life
IV Technical Papers on Self-Delimiting Programs
A theory of program size formally identical to information theory
Incompleteness theorems for random reals
Algorithmic entropy of sets
V Technical Papers on Blank-Endmarker Programs
Information-theoretic limitations of formal systems
A note on Monte Carlo primality tests and algorithmic information theory
Information-theoretic characterizations of recursive infinite strings
Program size, oracles, and the jump operation
VI Technical Papers on Turing Machines & LISP
On the length of programs for computing finite binary sequences
On the length of programs for computing finite binary sequences: statistical considerations
On the simplicity and speed of programs for computing infinite sets of natural numbers
VII Abstracts
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines II
Computational complexity and G?del’s incompleteness theorem
Computational complexity and G?del’s incompleteness theorem
Information-theoretic aspects of the Turing degrees
Information-theoretic aspects of Post’s construction of a simple set
On the difficulty of generating all binary strings of complexity less than
On the greatest natural number of definitional or information complexity
A necessary and sufficient condition for an infinite binary string to be recursive
There are few minimal descriptions
Information-theoretic computational complexity
A theory of program size formally identical to information theory
Recent work on algorithmic information theory
VIII Bibliography
Publications of G. Chaitin
Discussions of Chaitin’s work
Epilogue
Undecidability & randomness in pure mathematics
Algorithmic information & evolution
God not only plays dice in quantum mechanics, but even with the whole numbers! The discovery of randomness in arithmetic is presented in my book Algorithmic Information Theory published by Cambridge University Press. There I show that to decide if an algebraic equation in integers has finitely or infinitely many solutions is in some cases absolutely intractable. I exhibit an infinite series of such arithmetical assertions that are random arithmetical facts, and for which it is essentially the case that the only way to prove them is to assume them as axioms. This extreme form of G?del incompleteness theorem shows that some arithmetical truths are totally impervious to reasoning.
The papers leading to this result were published over a period of more than twenty years in widely scattered jouals, but because of their unity of purpose they fall together naturally into the present book, intended as a companion volume to my Cambridge University Press monograph. I hope that it will serve as a stimulus for work on complexity, randomness and unpredictability, in physics and biology as well as in metamathematics.
For the second edition, I have added the article Randomness in arithmetic (Part I), a collection of abstracts (Part VII), a bibliography (Part VIII), and, as an Epilogue, two essays which have not been published elsewhere that assess the impact of algorithmic information theory on mathematics and biology, respectively. I should also like to point out that it is straightforward to apply to LISP the techniques used in Part VI to study bounded-transfer Turing machines. A few footnotes have been added to Part VI, but the subject richly deserves book length treatment, and I intend to write a book about LISP in the near future.
I Introductory/Tutorial/Survey/Papers
Randomness and mathematical proof
Randomness in arithmetic
On the difficulty of computations
Information-theoretic computational complexity
Algorithmic information theory
Algorithmic information theory
II Applications to Metamathematics
G?del’s theorem and information
Randomness and G?del’s theorem
An algebraic equation for the halting probability
Computing the busy beaver function
III Applications to Biology
To a mathematical definition of life
Toward a mathematical definition of life
IV Technical Papers on Self-Delimiting Programs
A theory of program size formally identical to information theory
Incompleteness theorems for random reals
Algorithmic entropy of sets
V Technical Papers on Blank-Endmarker Programs
Information-theoretic limitations of formal systems
A note on Monte Carlo primality tests and algorithmic information theory
Information-theoretic characterizations of recursive infinite strings
Program size, oracles, and the jump operation
VI Technical Papers on Turing Machines & LISP
On the length of programs for computing finite binary sequences
On the length of programs for computing finite binary sequences: statistical considerations
On the simplicity and speed of programs for computing infinite sets of natural numbers
VII Abstracts
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines II
Computational complexity and G?del’s incompleteness theorem
Computational complexity and G?del’s incompleteness theorem
Information-theoretic aspects of the Turing degrees
Information-theoretic aspects of Post’s construction of a simple set
On the difficulty of generating all binary strings of complexity less than
On the greatest natural number of definitional or information complexity
A necessary and sufficient condition for an infinite binary string to be recursive
There are few minimal descriptions
Information-theoretic computational complexity
A theory of program size formally identical to information theory
Recent work on algorithmic information theory
VIII Bibliography
Publications of G. Chaitin
Discussions of Chaitin’s work
Epilogue
Undecidability & randomness in pure mathematics
Algorithmic information & evolution