## Information, Randomness & Incompleteness: Papers on Algorithmic Information TheoryThe 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 |

### Other editions - View all

### Common terms and phrases

algorithmic information theory apply axioms binary sequence binary string bits bound calculate Chaitin complexity concept Consider consisting construct contains defined definition denotes determine digits element entropy enumerate equal equation example exists fact finite binary sequences fixed follows formal system give given Godel's greater halts Hence immediately infinite information content initial integer interesting interval least Lemma length less limit log2 Logic mathematical means measure method minimal natural numbers needed Note number of bits observations obtain oracle organization output partial particular positive possible precisely Press probability problem proof propositions prove question random real number recursive function result rules running satisfies set of natural shown sim(C simulates Solovay specify square string sufficiently Suppose tape Theorem true Turing machine universal values yields York zero