G J Chaitin Home Page (original) (raw)

Sans les mathématiques on ne pénètre point au fond de la philosophie.Sans la philosophie on ne pénètre point au fond des mathématiques.Sans les deux on ne pénètre au fond de rien.— Leibniz [Without mathematics we cannot penetrate deeply into philosophy.Without philosophy we cannot penetrate deeply into mathematics.Without both we cannot penetrate deeply into anything.] Tribute to Leibniz: Essay on Leibniz, Complexity and Incompleteness

NOTICE: This website is being gradually phased out. My new website is hosted by Academia. Please visitGregory Chaitin Academia website. Thanks for your interest! However the LISP software for my three Springer books will not be moved to Academia. We intend to freeze this website, not remove it. — GJC, 22 January 2014

METABIOLOGY: Programming without a Programmer

Darwin's theory of evolution has been described as "design without a designer." Instead we study "programming without a programmer," that is, the evolution of randomly mutating software. We propose a toy model of evolution that can be studied mathematically: the new field of metabiology, which deals with randomly evolving artificial software (computer programs) instead of randomly evolving natural software (DNA).

[**Note on George Bernard Shaw (1856-1950)**: The first use of the term _metabiology_of which I am aware is in Shaw's 1921 play Back to Methuselah: A Metabiological Pentateuch. A better play of Shaw's that is also on evolution is his 1903 Man and Superman. Shaw's idea-filled plays, which feature lengthy prefaces, were originally meant to be read rather than performed.]

Ursula Molter, Gregory Chaitin and Hernán Lombardi opening the Buenos Aires Mathematics Festival (Argentina, May 2009)

Gregory Chaitin is well known for his work on metamathematics and for the celebrated Ω number, which shows that God plays dice in pure mathematics. He has published many books on such topics, including Meta Math! The Quest for Omega. His latest book, Proving Darwin: Making Biology Mathematical, attempts to create a mathematical theory of evolution and biological creativity. His least technical book is Conversations with a Mathematician.

Chaitin is a professor at the Federal University of Rio de Janeiro and an honorary professor at the University of Buenos Aires, and has honorary doctorates from the National University of Córdoba in Argentina and the University of Maine in the United States. He is also a member of the Académie Internationale de Philosophie des Sciences (Brussels) and the Leibniz-Sozietät der Wissenschaften (Berlin).

Carnival in Rio de Janeiro, 1970. Photo by Peter Albrecht

https://ufrj.academia.edu/GregoryChaitin

• Affiliation:
  UFRJ = Universidade Federal do Rio de Janeiro
  =Federal University of Rio de Janeiro (Brazil).
  Member, Advanced Studies Group,
  Production Engineering Program, COPPE/UFRJ.
• Honorary Titles:
  Honorary Professor, University of Buenos Aires (Argentina)
  Honorary Doctorate, University of Cordoba (Argentina)
  Honorary Doctorate, University of Maine (Orono)
• Academies:
  Académie Internationale de Philosophie des Sciences
  Leibniz-Sozietät der Wissenschaften zu Berlin
• Mailing address:
  G. J. Chaitin
  Room F110, Coppe/UFRJ
  P. O. Box 68507
  Rio de Janeiro, RJ 21.941-972
  BRAZIL

Latest Book Covers

Selected Papers

• Foreword for the Chinese edition of Proving Darwin
• IACAP 14 Invited Talk (Foils)
• Conceptual Complexity and Algorithmic Information(Preprint)
  "In this essay we propose that the fundamental philosophical concept of conceptual complexity
  is captured mathematically by the notion of algorithmic information content, and we discuss
  the complexity of physical and mathematical theories, the complexity of biological mutations,
  and the most complex system in biology, the human brain."
• Metabiología: los orígenes de la creatividad biológica(Investigación y Ciencia)
• Los límites de la razón (Investigación y Ciencia)
• The Limits of Reason (Scientific American)
• Randomness in Arithmetic (Russian Scientific American)
• L'Univers est-il intelligible? (La Recherche)
• Computers, Paradoxes and the Foundations of Mathematics (American Scientist)
• Ordenadores, paradojas y fundamentos de las matemáticas (Investigación y Ciencia)
• Grenzen der Berechenbarkeit (Spektrum der Wissenschaft)

Videos of Lectures

• Life as Evolving Software
  Universidade Federal do Rio Grande do Sul, 2 May 2011
• Hacia una teoría matemática de la evolución y de la creatividad biológica
  Instituto de Sistemas Complejos de Valparaíso, 30 de noviembre 2010
• Leibniz, Complexity and Incompleteness
  Hebrew University, Jerusalem, 13 September 2008

Books

• Algorithmic Information Theory, Cambridge University Press, 1987.
• Information, Randomness and Incompleteness: Papers on Algorithmic Information Theory, World Scientific, 1987, 2nd edition, 1990.
• Information-Theoretic Incompleteness, World Scientific, 1992.
• The Limits of Mathematics: A Course on Information Theory and the Limits of Formal Reasoning, Springer, 1998. Also in Japanese.
• The Unknowable, Springer, 1999. Also in Japanese.
• Exploring Randomness, Springer, 2001.
• Conversations with a Mathematician: Math, Art, Science and the Limits of Reason, Springer, 2002. Also in Portuguese and Japanese.
• From Philosophy to Program Size: Key Ideas and Methods. Lecture Notes on Algorithmic Information Theory from the 8th Estonian Winter School in Computer Science, EWSCS '03, Tallinn Institute of Cybernetics, 2003.
• Meta Math! The Quest for Omega, Pantheon, 2005. Also UK, French, Italian, Portuguese, Japanese, Greek and Spanish editions.
• With Ugo Pagallo,Teoria algoritmica della complessità, Giappichelli, 2006.
• Thinking about Gödel and Turing: Essays on Complexity, 1970-2007, World Scientific, 2007.
• Matemáticas, Complejidad y Filosofía / Mathematics, Complexity and Philosophy (bilingual Spanish/English edition), Midas, 2011.
• With Newton da Costa and Francisco Antonio Doria,Gödel's Way: Exploits into an Undecidable World, CRC Press, 2012.
• Proving Darwin: Making Biology Mathematical, Pantheon, 2012. Also in Spanish, Italian, Japanese and Chinese.
  Warning: the e-book version was not sent to the author for proofreading and has many errors in the formulas.

LISP Software for Springer Books

• LISP interpreter as Java applet
• LISP interpreter in C
• LISP interpreter in Mathematica(Original Mma v2 version)
• LISP interpreter in Mathematica(Mma v4.1 version contributed by Joe Yoon)
• LISP Tutorial (from The Unknowable)
• LISP Manual (from Exploring Randomness)
• LISP Manual—Advanced Features (from Exploring Randomness)

The Limits of Mathematics (1998)

LISP Code

• "Manual" for our LISP (alternate version)
• You can't prove that an S-expression is elegant! (commented version)
• The universal Turing machine used to define our complexity measure H (alternate version)
• You can't prove lower bounds on the complexity H! (commented version)
• Ω in the limit from below—stupid version (with additional output)
• Ω in the limit from below—elegant version (with additional output)
• Ω in the limit from below—fast version
• Ω is algorithmically incompressible/random (commented version)
• You can't prove what Ω's bits are! (commented version)

LISP Runs

• "Manual" for our LISP (alternate version)
• You can't prove that an S-expression is elegant! (commented version)
• The universal Turing machine used to define our complexity measure H (alternate version)
• You can't prove lower bounds on the complexity H! (commented version)
• Ω in the limit from below—stupid version (with additional output)
• Ω in the limit from below—elegant version (with additional output)
• Ω in the limit from below—fast version
• Ω is algorithmically incompressible/random (commented version)
• You can't prove what Ω's bits are! (commented version)

The Unknowable (1999)

LISP Code

• Elementary set theory in LISP
• A self-reproducing LISP expression
• Gödel's proof of his incompleteness theorem
• Turing's proof of the unsolvability of the halting problem
• My proof that you can't show that a LISP expression is elegant

LISP Runs

• Elementary set theory in LISP
• A self-reproducing LISP expression
• Gödel's proof of his incompleteness theorem
• Turing's proof of the unsolvability of the halting problem
• My proof that you can't show that a LISP expression is elegant

Exploring Randomness (2001)

• Preface

Part 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
  utm2 code,utm2 run

Part II—Program-Size

• A self-delimiting Turing machine considered as a set of (program, output) pairs
  exec code,exec run
• How to construct self-delimiting Turing machines: the Kraft inequality
  kraft code,kraft run
• The connection between program-size complexity and algorithmic probability: H(x)=−log_2P(x)+O(1)H(x) = -\log_2 P(x) + O(1)H(x)=−log_2P(x)+O(1).
  Occam's razor: there are few minimum-size programs
  occam code,occam run
• The basic result on relative complexity: H(y∣x)=H(x,y)−H(x)+O(1)H(y|x) = H(x, y) - H(x) + O(1)H(y∣x)=H(x,y)−H(x)+O(1)
  decomp code,decomp run,lemma code,lemma run

Part III—Randomness

• Theoretical interlude—What is randomness? My definitions
• Proof that Martin-Löf randomness is equivalent to Chaitin randomness
  martin-lof code,martin-lof run,martin-lof2 code,martin-lof2 run
• Proof that Solovay randomness is equivalent to Martin-Löf randomness
  solovay code,solovay run
• Proof that Solovay randomness is equivalent to strong Chaitin randomness
  chaitin code,chaitin run,chaitin2 code,chaitin2 run

Part 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

\[ \Omega = \sum_{\text{program ppp halts}} 2^{-(\text{size in bits of ppp})} \] \[ \Omega_U = \sum_{\text{$U(p)$ halts}} 2^{-|p|} \] \[ \Omega' = \sum_{n \,=\, 1,\, 2,\, 3,\, ...} 2^{-H(n)} \]