Exploring RANDOMNESS
Springer London Ltd (Verlag)
978-1-85233-417-8 (ISBN)
I Introduction.- Historical introduction—A century of controversy over the foundations of mathematics.- What is LISP? Why do I like it?.- How to program my universal Turing machine in LISP.- II Program Size.- A self-delimiting Turing machine considered as a set of (program, output) pairs.- How to construct self-delimiting Turing machines: the Kraft inequality.- The connection between program-size complexity and algorithmic probability: H(x) = ? log2P(x) +O(1). Occam’s razor: there are few minimum-size programs.- The basic result on relative complexity: H(y?x) = H(x,y)-H(x)+O(1).- III Randomness.- Theoretical interlude—What is randomness? My definitions.- Proof that Martin-Löf randomness is equivalent to Chaitin randomness.- Proof that Solovay randomness is equivalent to Martin-Löf randomness.- Proof that Solovay randomness is equivalent to strong Chaitin randomness.- IV Future Work.- Extending AIT to the size of programs for computing infinite sets and to computations with oracles.- Postscript—Letter to a daring young reader.
Erscheint lt. Verlag | 30.7.2001 |
---|---|
Reihe/Serie | Discrete Mathematics and Theoretical Computer Science |
Zusatzinfo | X, 164 p. |
Verlagsort | England |
Sprache | englisch |
Maße | 155 x 235 mm |
Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
ISBN-10 | 1-85233-417-7 / 1852334177 |
ISBN-13 | 978-1-85233-417-8 / 9781852334178 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
aus dem Bereich