DeepRead
Cover of Exploring randomness

Exploring randomness

Gregory J. Chaitin · 2001

Mathematics and physics › Infinity and logic for general readers

#13,996 most recommended

About the book

The subject is algorithmic information theory, which measures the complexity of a string by the size of the shortest program that produces it. The book is an informal, lecture-style exposition that uses small LISP programs as its working language and draws on computability, information theory and the foundations of mathematics. Its scope is the mathematics of randomness and the limits of formal reasoning rather than practical computing. Chaitin argues that randomness is not confined to physics or probability but appears inside pure mathematics, so some arithmetical facts cannot be compressed or derived from any finite set of axioms. His main example is the halting probability Omega, a real number whose binary digits are algorithmically random and can be defined but not computed. From this he claims that incompleteness follows from information content: a formal system with a given amount of information can settle only finitely many of Omega's digits.

Written by Claude from what it knows of this book.

What Hacker News says 100% recommend · 0% critical

012201620182020202220252016 peak · 1
This bookAverage book in Infinity and logic for general readers

In the commenters’ own words

What Open Library readers say

No Open Library reader has rated it yet.

  • 3 want to read
  • 0 reading
  • 0 have read

Open Library’s page for the book

What critics say, via Wikipedia

No Wikipedia article about this book yet, so no critics to quote.

Reddit communities — coming later

Details

First published
2001
ISBN
9781852334178
Editions known
6 at Open Library
Open Library
OL17946004W

Computational complexityLISP (Computer program language)Machine theory

Explore in the mosaic

Read next: its neighbours on the mosaic

  • Meta Math!
    Gregory Chaitin · 2005 · recommended by 11 people · similar by subject and what people say about it
  • Turtles, termites, and traffic jams
    Mitchel Resnick · 1994 · recommended by 9 people · loosely similar by subject
  • Meta maths
    Gregory J. Chaitin · 2006 · recommended by 1 person · similar by subject and what people say about it
  • The Limits of Mathematics
    Gregory J. Chaitin · 1997 · recommended by 2 people · similar by subject and what people say about it
  • The Mathematical Experience
    Philip J. Davis · 1980 · recommended by 20 people · 2 people recommended both
  • Algorithmic information theory
    Gregory J. Chaitin · 1987 · recommended by 1 person · similar by subject and what people say about it
  • Things a Computer Scientist Rarely Talks About
    Donald Knuth · 2001 · recommended by 9 people · similar by subject and what people say about it
  • Probability Theory
    E. T. Jaynes · 2003 · recommended by 77 people · similar by subject and what people say about it
  • Why people believe weird things
    Michael Shermer · 1997 · recommended by 9 people · loosely similar by subject
  • Turtle geometry
    Harold Abelson · 1981 · recommended by 15 people · loosely similar by subject
  • Chaos
    James Gleick · 1987 · recommended by 45 people · similar by subject and what people say about it
  • Godel's theorem simplified
    Harry J. Gensler · 1984 · recommended by 2 people · loosely similar by subject
  • An introduction to information theory
    John Robinson Pierce · 1980 · recommended by 15 people · similar by subject and what people say about it
  • The craft of Prolog
    Richard A. O'Keefe · 1990 · recommended by 18 people · loosely similar by subject
  • Theory of computation
    Michael Sipser · 2007 · recommended by 14 people · similar by subject and what people say about it
  • Chance and chaos
    David Ruelle · 1991 · recommended by 3 people · similar by subject and what people say about it
  • Surreal numbers
    Donald Knuth · 1974 · recommended by 27 people · similar by subject and what people say about it
  • The art of computer programming
    Donald Knuth · 1968 · recommended by 336 people · similar by subject and what people say about it
  • Good and real
    Gary L. Drescher · 2006 · recommended by 8 people · similar by subject and what people say about it
  • Quantum Computing for Everyone
    Chris Bernhardt · 2019 · recommended by 3 people · similar by subject and what people say about it
  • Does God play dice?
    Ian Stewart · 1989 · recommended by 1 person · similar by subject and what people say about it
  • Chaos and fractals
    Heinz-Otto Peitgen · 1992 · recommended by 4 people · similar by subject and what people say about it
  • Proofs and refutations
    Imre Lakatos · 1976 · recommended by 34 people · similar by subject and what people say about it
  • The logic of chance
    Eugene V. Koonin · 2011 · recommended by 2 people · similar by subject and what people say about it