Looking for an examination copy?
This title is not currently available for examination. However, if you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact email@example.com providing details of the course you are teaching.
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.
Be the first to review this book
- Date Published: December 2004
- format: Paperback
- isbn: 9780521616041
- length: 192 pages
- dimensions: 246 x 189 x 10 mm
- weight: 0.35kg
- availability: Manufactured on demand: supplied direct from the printer
Table of Contents
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
You are now leaving the Cambridge University Press website, your eBook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.Continue ×