Information and Randomness: An Algorithmic Perspective

✍ Scribed by Cristian Calude

• Publisher: Springer
• Year: 1994
• Tongue: English
• Leaves: 251
• Series: Monographs in Theoretical Computer Science. An EATCS Series
• Edition: 1st
• Category: Library

✦ Synopsis

"Algorithmic information theory (AIT) is the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously", says G.J. Chaitin, one of the fathers of this theory of complexity and randomness, which is also known as Kolmogorov complexity. It is relevant for logic (new light is shed on G"del's incompleteness results), physics (chaotic motion), biology (how likely is life to appear and evolve?), and metaphysics (how ordered is the universe?). This book, benefiting from the author's research and teaching experience in Algorithmic Information Theory (AIT), should help to make the detailed mathematical techniques of AIT accessible to a much wider audience.

✦ Table of Contents

Front Matter....Pages I-XVI
Mathematical Background....Pages 1-14
Noiseless Coding....Pages 15-24
Program Size....Pages 25-39
Recursively Enumerable Instantaneous Codes....Pages 41-70
Random Strings....Pages 71-106
Random Sequences....Pages 107-182
Applications....Pages 183-216
Open Problems....Pages 217-219
Back Matter....Pages 221-243

✦ Subjects

Mathematical Logic and Formal Languages; Coding and Information Theory; Probability Theory and Stochastic Processes; Statistics, general; Algorithm Analysis and Problem Complexity; Computational Mathematics and Numerical Analysis