Descripciones mejoradas de Syndetics:

Chaitin, the inventor of algorithmic information theory, presents in this book 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 the halting probability of a universal computer if its program is chosen by tossing a coin. The other half is concerned with encoding the halting probability as an algebraic equation in integers, a so-called exponential diophantine equation.

Tabla de contenidos provista por Syndetics

• Foreword
• Preface
• Figures
• 1 Introduction
• Part I Formalisms for Computation: Register Machines, Exponential Diophantine Equations, and Pure LISP
• 2 The arithmetization of register machines
• 3 A version of Pure LISP
• 4 The LISP interpreter EVAL
• Part II Program Size, Halting Probabilities, Randomness, and Metamathematics
• 5 Conceptual development
• 6 Program size
• 7 Randomness
• 8 Incompleteness
• 9 Conclusion
• Bibliography

Reseñas proporcionadas por Syndetics

CHOICE Review

A statement and proof of Chaitin's version of Godel's incompleteness theorem. One might say that the book is algorithmically inexplicable, in that a really adequate review of it would be considerably longer than the text itself, exploring the questions it raises. To quote the author, "...{{R}}andomness and unpredictability not only occur in nonlinear dynamics and quantum mechanics, but even in rather elementary branches of number theory." With the end in mind of exhibiting an algebraic equation for which the number of solutions jumps from finite to infinite as a parameter is varied, Chaitin has encoded the halting probability into an exponential diophantine equation. To do this he employs a version of LISP. Although knowledge of LISP, the theories of recursive functions, and of probability is helpful, the text is essentially self-contained, as Chaitin provides brief but adequate background for everything he does. One could say that the pages of LISP program segments in sections 4.4 and 4.5 are excessive since they are not complete, but the author offers complete documentation (292 pages of it) to anyone requesting it. The absence of an index is regrettable. This absorbing and delightful book is the ideal volume to recommend to the bright, thoughtful student looking for challenge. Highly recommended. -R. J. Wernick, San Francisco State University