s p o n s o r e d   l i n k s


Algorithmic Information Theory.pdf

November 6, 2009 · Filed Under Other Programming Ebooks  · Tags: , , , , , ,

Taken from Preface: The aim of this book is to present the strongest possible version of Godel’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 of the book is concerned with encoding as an algebraic equation in integers, a so-called exponential diophantine equation.

Godel’s original proof of his incompleteness theorem is essentially the assertion that one cannot always prove that a program will fail to halt. This is equivalent to asking whether it ever produces any output.

He then converts this into an arithmetical assertion. Over the years this has been improved; it follows from the work on Hilbert’s 10th problem that Godel’s theorem is equivalent to the assertion that one cannot always prove that a diophantine equation has no solutions if this is the case.

In our approach to incompleteness, we shall ask whether or not a program produces an infinite amount of output rather than asking whether it produces any; this is equivalent to asking whether or not a diophantine equation has infinitely many solutions instead of asking whether or not it is solvable.

If one asks whether or not a diophantine equation has a solution for N diff erent values of a parameter, the N di erent answers to this question are not independent; in fact, they are only log2 N bits of information.

But if one asks whether or not there are infinitely many solutions for N di erent values of a parameter, then there are indeed cases in which the N di fferent answers to these questions are independent mathematical facts, so that knowing one answer is no help in knowing any of the others. The equation encoding
has this property. When mathematicians can’t understand something they usually assume that it is their fault, but it may just be that there is no pattern or law to be discovered!

How to read this book: This entire monograph is essentially a proof of one theorem, Theorem D in Chapter 8. The exposition is completely self-contained, but the collection Chaitin (1987c) is a useful source of background material. While the reader is assumed to be familiar with the basic concepts of recursive function or computability theory and probability theory, at a level easily acquired from Davis (1965) and Feller (1970), we make no use of individual results from these fields that we do not reformulate and prove here. Familiarity with LISP programming is helpful but not necessary, because we give a selfcontained exposition of the unusual version of pure LISP that we use, including a listing of an interpreter. For discussions of the history and significance of metamathematics, see Davis (1978), Webb (1980), Tymoczko (1986), and Rucker (1987).

Although the ideas in this book are not easy, we have tried to present the material in the most concrete and direct fashion possible. We give many examples, and computer programs for key algorithms. In particular, the theory of program-size in LISP presented in Chapter 5 and Appendix B, which has not appeared elsewhere, is intended as an illustration of the more abstract ideas in the following chapters.

Author: G J Chaitin IBM, P O Box 218 Yorktown Heights, NY 10598.

Contents:

  •  
    • 1 Introduction
  • I Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP
    • 2 Register Machines [ Introduction ~ Pascal's TriangleMod 2 ~ LISP RegisterMachines ~ Variables Used in Arithmetization ~ An Example of Arithmetization ~ A Complete Example of Arithmetization ~ Expansion of )'s ~ Left-Hand Side ~ Right-Hand Side ]
    • 3 A Version of Pure LISP [ Introduction ~ Definition of LISP ~ Examples ~ LISP in LISP I ~ LISP in LISP II ~ LISP in LISP III ]
    • 4 The LISP Interpreter EVAL [ RegisterMachine Pseudo-Instructions ~ EVAL in RegisterMachine Language ~ The Arithmetization of EVAL ~ Start of Left-Hand Side ~ End of Right-Hand Side ]
  • II Program Size, Halting Probabilities, Randomness, & Metamathematics
    • 5 Conceptual Development [ Complexity via LISP Expressions ~ Complexity via Binary Programs ~ Self-Delimiting Binary Programs ~ Omega in LISP ]
    • 6 Program Size [ Introduction ~ Definitions ~ Basic Identities ~ RandomStrings ]
    • 7 Randomness [ Introduction ~ RandomReals ]
    • 8 Incompleteness [ Lower Bounds on Information Content ~ RandomReals: First Approach ~ Random Reals: jAxiomsj ~ RandomReals: H(Axioms) ]
    • 9 Conclusion
    • 10 Bibliography
    • Implementation Notes
    • S-expressions of Size N
    • Back Cover
  • Figures:
    • Pascal’s Triangle
    • Pascal’s TriangleMod 2
    • Pascal’s Triangle Mod 2 with 0’s Replaced by Blanks
    • RegisterMachine Instructions
    • A RegisterMachine Program
    • The LISP Character Set
    • A LISP Environment
    • Atoms with Implicit Parentheses
    • RegisterMachine Pseudo-Instructions

This computer science ebook is available FREE at GJ Chaitin website, we merely collect the information, Online Free Ebooks neither affiliated with the author(s), the website and any brand nor responsible for its content and change of content. (Read our disclaimer here or here before you download the document from the website written above by clicking the below link).

Download free Algorithmic Information Theory.pdf (236 pages pdf file, 1 MB).

Related posts




You might also be interested in reading:
computer science, free download ebooks computer science, free downloads computer science, free ebooks for computer science basic level, information theory pdf, free book (computer theory), computer science books free download, www freedownloadebook net, e net theorem pdf, freedownload ebook computer
« Prev

Disclaimer

http://www.onlinefreeebooks.net - provides you collection of links to other websites containing ebooks/manuals/cheatsheets either for computer geeks, technicians, automotive enthusiasts or programmers. We merely take the power of Google Search to find those materials and link to it. NONE OF THOSE MATERIALS ARE HOSTED IN THIS SERVER NOR UPLOADED BY ME IN SOMEONE'S SERVERS.

We are neither affiliated with authors and brands nor responsible for its content and change of content.

Information contained herein is provided "as is" without warranty of any kind, either expressed or implied, including any warranty of merchantability or fitness for a particular purpose. In no event shall ANYONE be held liable for any loss of profit, special, incidental, consequential, or other similar claims.

Comments

Leave a Reply