Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory

Front Cover
World Scientific, 1987 - Computers - 272 pages
The papers gathered in this book were published over a period of more than twenty years in widely scattered journals. They led to the discovery of randomness in arithmetic which was presented in the recently published monograph on ?Algorithmic Information Theory? by the author. There the strongest possible version of G del's incompleteness theorem, using an information-theoretic approach based on the size of computer programs, was discussed. The present book is intended as a companion volume to the monograph and it will serve as a stimulus for work on complexity, randomness and unpredictability, in physics and biology as well as in metamathematics.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Randomness and mathematical proof Scientific American 1975
3
On the difficulty of computations IEEE Transactions on Information Theory 1970
14
Informationtheoretic computational complexity IEEE Transactions
23
Algorithmic information theory Encyclopedia of Statistical Sciences 1982
33
Godels theorem and information International Journal of Theoretical Physics 1982
55
Randomness and Godels theorem Proceedings 1985 Solvay Conference in press
66
To a mathematical definition of life ACM SICACT News 1970
79
Toward a mathematical definition of life The Maximum Entropy Formalism 1979
86
Incompleteness theorems for random reals Advances in Applied Mathematics 1987
123
Algorithmic entropy of sets Computers Mathematics with Applications 1976
147
Informationtheoretic limitations of formal systems Journal of the ACM 1974
165
A note on Monte Carlo primality tests and algorithmic information theory
191
Informationtheoretic characterizations of recursive infinite strings Theoretical Computer
197
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information