cdc-coteauxdegaronne
» » Information and Randomness: An Algorithmic Perspective (EATCS Monographs in Theoretical Computer Science)
eBook Information and Randomness: An Algorithmic Perspective (EATCS Monographs in Theoretical Computer Science) ePub

eBook Information and Randomness: An Algorithmic Perspective (EATCS Monographs in Theoretical Computer Science) ePub

by Cristina S. Calude,Gregory J. Chaitin

  • ISBN: 3540574565
  • Category: Computer Science
  • Subcategory: Computers
  • Author: Cristina S. Calude,Gregory J. Chaitin
  • Language: English
  • Publisher: Springer-Verlag Berlin and Heidelberg GmbH & Co. K (November 1994)
  • Pages: 256
  • ePub book: 1317 kb
  • Fb2 book: 1280 kb
  • Other: lrf txt doc lit
  • Rating: 4.6
  • Votes: 583

Description

Book · November 2002 with 21 Reads .

Book · November 2002 with 21 Reads. Cite this publication. University of Auckland. This extension known as Kraft-Chaitin Theorem, was obtained by G. J. Chaitin in his seminal paper. The aim of this note is to offer a simpler proof of Kraft-Chaitin Theorem based on a new construction of the prefix-free code.

I stumbled over this (lovely) book a little by accident. As I kept reading, my enthusiasm for the book gradually increased. While the book is addressed perhaps more to students in computation and in CS, it is very attractive also as a text to be used in mainstream mathematics, and in probability theory. The main portion in the book focuses on classical and modern topics in computability, and its connections to randomness; covering concrete halting problems, chaos, cellular automata, algorithms, and their complexity. Palle Jorgensen, October 2004.

Information And Randomness book. Algorithmic information theory (AIT) is the result of putting.

Algorithmic information theory (AIT) is a "merger of information theory and computer science" that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically gener.

Algorithmic information theory (AIT) is a "merger of information theory and computer science" that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure.

Monographs in Theoretical Computer Science . 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 . Chaitin, one of the fathers of this theory of complexity and randomness, which is also known as Kolmogorov complexity. Show all. Table of contents (8 chapters).

The present book by Calude fits very well in our series.

EATCS monographs on theoretical computer science. Summary: An introduction to algorithmic information theory, which is relevant to the study of logic, physics, biology and metaphysics.

Information and Randomness: An Algorithmic Perspective, (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag, Berlin, 2002. 1966) On the Length of Programs for Computing Finite Binary Sequences, J. Association for Computing Machinery, v. 13, No. 4, pp. 547–569. 1969) On the Simplicity and Speed of Programs for Computing Definite Sets of Natural Numbers, J. 16, pp. 407–412.

"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.

Related to Information and Randomness: An Algorithmic Perspective (EATCS Monographs in Theoretical Computer Science)

Comments

Cozius Cozius
I stumbled over this (lovely) book a little by accident. As I kept reading, my enthusiasm for the book gradually increased. While the book is addressed perhaps more to students in computation and in CS, it is very attractive also as a text to be used in mainstream mathematics, and in probability theory.

It begins with a new look at the classical Kolmogorov construction of measures on infinite product spaces, and asks for explicit ways of labeling them with a class of certain concrete numerical functions. Then it moves onto noiseless coding theory (from communications science), but it stays rooted firmly in classical ideas from Shannon-Kolmogorov communication and information theory.

It is indeed pleasing to see that God still plays dice, not only in quantum theory, but also in such classical areas of math as in number theory.

From the foreword: "...putting Shannon's information theory and Turing's computability theory into a cocktail shaker, and shaking vigorously..."

The book is a second edition 2002, with a number of attractive additions to the first edition from 1994. It will likely work equally well in a course, as for self-study.

The main portion in the book focuses on classical and modern topics in computability, and its connections to randomness; covering concrete halting problems, chaos, cellular automata, algorithms, and their complexity.

Palle Jorgensen, October 2004.
Use_Death Use_Death
"Information and Randomness: An Algorithmic Perspective" is an outstanding book on Algorithmic Information Theory that is accessible to students and useful to active researchers.

Cristian Calude is a prolific researcher in this field.