Информатика и вычислительная техника
  • формат pdf
  • размер 1.76 МБ
  • добавлен 18 октября 2011 г.
Chaitin G.J. Information Randomness and Incompleteness. Papers on Algorithmic Information Theory
Издательство 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
Undecidability & randomness in pure mathematics
Algorithmic information & evolution
Смотрите также

Chaitin G.J. Algorithmic information theory

  • формат pdf
  • размер 949.53 КБ
  • добавлен 26 августа 2011 г.
Publisher: Cambridge University Press ISBN: 0521343062 Pages : 236 Publication Date : April 2, 2003 Book Excerpts: The aim of this book is to present the strongest possible version of G?del's incompleteness theorem, using an information-theoretic approach based on the size of computer programs. One half of the book is concerned with studying Omega, the halting probability of a universal computer if its program is chosen by tossing a coin....

Chaitin G.J. The Limits of Mathematics

  • формат djvu
  • размер 847.99 КБ
  • добавлен 22 марта 2011 г.
Springer, 1997. - 147 pages. This book is the final version of a course on algorithmic information theory and the epistemology of mathematics and physics. It discusses Einstein and Goedel's views on the nature of mathematics in the light of information theory, and sustains the thesis that mathematics is quasi-empirical. There is a foreword by Cris Calude of the University of Auckland, and supplementary material is available at the author's web s...

Cover T.M., Thomas J.A. Elements of Information Theory

  • формат pdf
  • размер 34.35 МБ
  • добавлен 06 января 2012 г.
Wiley series in telecommunications. John Wiley & Sons, Inc., 1991. – 563 pages. This is intended to be a simple and accessible book on information theory. As Einstein said, ’’Everything should be made as simple as possible, but no simpler.’’ This point of view drives our development throughout the book. We were drawn to the field of information theory from backgrounds in communication theory, probability theory and statistics, because of the...

Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

  • формат pdf
  • размер 4.74 МБ
  • добавлен 01 ноября 2011 г.
Cаmbridge Univеrsity Prеss, 2009, 691 pages Information theory lies at the heart of modern technology, underpinning all communications, networking, and data storage systems. This book sets out, for the first time, a complete overview of both classical and quantum information theory. Throughout, the reader is introduced to key results without becoming lost in mathematical details. Opening chapters present the basic concepts and various applicati...

Gray R.M. Entropy and Information Theory

  • формат pdf
  • размер 2.58 МБ
  • добавлен 07 апреля 2011 г.
2nd Edition Springer, 2011. 409 p. ISBN:1441979697 This book is an updated version of the information theory classic, first published in 1990. About one-third of the book is devoted to Shannon source and channel coding theorems; the remainder addresses sources, channels, and codes and on information and distortion measures and their properties. New in this edition: Expanded treatment of stationary or sliding-block codes and their relations to...

Hamming R.W. Coding and Information Theory

  • формат djvu
  • размер 1.71 МБ
  • добавлен 17 апреля 2011 г.
Prentice Hall, 1986. - 272 pages. Preface to the First Edition: This book combines the fields of coding and information theory in a natural way. They are both theories about the representation of abstract symbols. The two fields are now each so vast that only the elements can be presented in a short book. Information theory is usually thought of as "sending information from here to there" (transmission of information), but this is exactly the...

Hirsch M.J., Pardalos P.M., Murphey R. Dynamics of Information Systems: Theory and Applications

  • формат pdf
  • размер 9.26 МБ
  • добавлен 29 августа 2011 г.
Sрringer, 2010. - 371 p. "Dynamics of Information Systems" presents state-of-the-art research explaining the importance of information in the evolution of a distributed or networked system. This book presents techniques for measuring the value or significance of information within the context of a system. Each chapter reveals a unique topic or perspective from experts in this exciting area of research. These newly developed techniques have numer...

Kullback S. Information Theory and Statistics

  • формат pdf
  • размер 15.7 МБ
  • добавлен 16 января 2011 г.
Peter Smith, 1978. - 399 pages. Highly useful text studies the logarithmic measures of information and their application to testing statistical hypotheses. Topics include introduction and definition of measures of information, their relationship to Fisher’s information measure and sufficiency, fundamental inequalities of information theory, much more. Numerous worked examples and problems.

Sommaruga G (ed.) Formal Theories of Information. From Shannon to Semantic Information Theory and General Concepts of Information

  • формат pdf
  • размер 2.63 МБ
  • добавлен 06 декабря 2011 г.
Издательство Springer, 2009, -274 pp. It is commonly assumed that computers process information. But what is information? In a technical, important, but nevertheless rather narrow sense, Shannon’s information theory gives a first answer to this question. This theory focuses on measuring the information content of a message. Essentially this measure is the reduction of the uncertainty obtained by receiving a message. The uncertainty of a situatio...

Thomas M. Cover, Joy A. Thomas. Elements of information theory

  • формат pdf
  • размер 10.09 МБ
  • добавлен 01 декабря 2009 г.
2nd ed. John Wiley & Sons, Inc. This book has arisen from over ten years of lectures in a two-quarter sequence of a senior and first-year graduate-level course in information theory, and is intended as an introduction to information theory for students of communication theory, computer science, and statistics. The first quarter might cover Chapters 1 to 9, which includes the asymptotic equipartition property, data compression, and channel...