Gregory Chaitin: Difference between revisions
Jump to navigation
Jump to search
imported>LWG cleanup and elimination of WP:Critsection |
imported>Plinthist Clean up infobox. |
||
| Line 2: | Line 2: | ||
{{Use dmy dates|date=September 2020}} | {{Use dmy dates|date=September 2020}} | ||
{{Infobox scientist | {{Infobox scientist | ||
|name = Gregory Chaitin | | name = Gregory Chaitin | ||
|image = Gregory Chaitin hiking.jpg | | image = Gregory Chaitin hiking.jpg | ||
|caption = Chaitin in 2008 | | caption = Chaitin in 2008 | ||
|birth_date = {{birth date and age |df=yes|1947|6|25}} | | birth_date = {{birth date and age |df=yes|1947|6|25}} | ||
|birth_place = [[Chicago]]<ref>[ | | birth_place = [[Chicago]]<ref>[https://arxiv.org/pdf/math/0701164 Gregory Chaitin (2007), Algorithmic information theory: "Chaitin Research Timeline"]</ref> | ||
|death_date = | | death_date = | ||
|death_place = | | death_place = | ||
| fields = {{ubl|[[Biology]]|[[Mathematics]]|[[Computer science]]}} | |||
| workplaces = {{Plainlist| | |||
|fields = {{ubl|[[Biology]]|[[Mathematics]]|[[Computer science]]}} | |||
|workplaces = {{Plainlist| | |||
* [[Mohammed VI Polytechnic University]] | * [[Mohammed VI Polytechnic University]] | ||
* [[Federal University of Rio de Janeiro]] | * [[Federal University of Rio de Janeiro]] | ||
| Line 18: | Line 16: | ||
* [[IBM T.J. Watson Research Center]] | * [[IBM T.J. Watson Research Center]] | ||
}} | }} | ||
|alma_mater = <!--None, he did not complete CUNY--> | | alma_mater = <!--None, he did not complete CUNY--> | ||
|doctoral_advisor = <!--None--> | | doctoral_advisor = <!--None--> | ||
|academic_advisors = <!--None--> | | academic_advisors = <!--None--> | ||
|doctoral_students = | | doctoral_students = | ||
|notable_students = | | notable_students = | ||
|known_for = {{ubl|[[Algorithmic | | known_for = {{ubl|[[Algorithmic information theory]]|[[Chaitin's constant]]|[[Chaitin's algorithm]]}} | ||
|influences = | | influences = | ||
|influenced = | | influenced = | ||
|awards = | | awards = | ||
|website = | | website = | ||
|religion = | | religion = | ||
|signature = | | signature = <!--(filename only)--> | ||
|footnotes = | | footnotes = | ||
}} | }} | ||
'''Gregory John Chaitin''' ({{IPAc-en|ˈ|tʃ|aɪ|t|ɪ|n}} {{respell|CHY|tin}}; born 25 June 1947) <!-- Could we get a more specific place and time? --> is an [[Argentina|Argentine]]-[[United States|American]] [[mathematician]] and [[computer scientist]]. | '''Gregory John Chaitin''' ({{IPAc-en|ˈ|tʃ|aɪ|t|ɪ|n}} {{respell|CHY|tin}}; born 25 June 1947) <!-- Could we get a more specific place and time? --> is an [[Argentina|Argentine]]-[[United States|American]] [[mathematician]] and [[computer scientist]]. His work was foundational to the development of [[algorithmic information theory]], and has been influential on [[metamathematics]].<ref>{{cite book|title=Information and Randomness: An Algorithmic Perspective|last=Calude|first=C.S.|publisher=Springer-Verlag|year=2002|series=Texts in Theoretical Computer Science. An EATCS Series}}</ref><ref>R. Downey, and D. Hirschfeldt (2010), ''Algorithmic Randomness and Complexity'', Springer-Verlag.</ref> He independently discovered what is today known as algorithmic (Kolmogorov or Solomonoff–Kolmogorov–Chaitin) [[Kolmogorov complexity|complexity]] simultaneously with [[Andrei Kolmogorov]] and [[Ray Solomonoff]].<ref>Panu Raatikainen, "Exploring Randomness and The Unknowable" | ||
[https://www.ams.org/notices/200109/rev-panu.pdf ''Notices'' of the American Mathematical Society] Book Review October 2001.</ref> | [https://www.ams.org/notices/200109/rev-panu.pdf ''Notices'' of the American Mathematical Society] Book Review October 2001.</ref> | ||
==Mathematics and computer science== | ==Mathematics and computer science== | ||
Gregory Chaitin is [[Jewish]]. He attended the [[Bronx High School of Science]] and the [[City College of New York]], where he (still in his teens) developed the theory that led to his independent discovery of [[Kolmogorov complexity|algorithmic complexity]].<ref>{{Citation |last1=Li |last2=Vitanyi |title=An Introduction to Kolmogorov Complexity and Its Applications |publisher=Springer |year=1997 |url=https://books.google.com/books?id=LKEmB_GQ53QC |page=92 |quote=G.J.Chaitin had finished the Bronx High School of Science, and was an 18-year-old undergraduate student at City College of the City University of New York, when he submitted two papers.... In his [second] paper, Chaitin puts forward the notion of Kolmogorov complexity.... |isbn=9780387948683 }}</ref><ref>{{Citation |last=Chaitin |first=G. J. |title=On the Length of Programs for Computing Finite Binary Sequences |journal=Journal of the ACM |volume=13 |issue=4 |date=October 1966 |pages=547–569 |doi=10.1145/321356.321363|s2cid=207698337 }}</ref> | Gregory Chaitin is [[Jewish]]. He attended the [[Bronx High School of Science]] and the [[City College of New York]], where he (still in his teens) developed the theory that led to his independent discovery of [[Kolmogorov complexity|algorithmic complexity]].<ref>{{Citation |last1=Li |last2=Vitanyi |title=An Introduction to Kolmogorov Complexity and Its Applications |publisher=Springer |year=1997 |url=https://books.google.com/books?id=LKEmB_GQ53QC |page=92 |quote=G.J.Chaitin had finished the Bronx High School of Science, and was an 18-year-old undergraduate student at City College of the City University of New York, when he submitted two papers.... In his [second] paper, Chaitin puts forward the notion of Kolmogorov complexity.... |isbn=9780387948683 }}</ref><ref>{{Citation |last=Chaitin |first=G. J. |title=On the Length of Programs for Computing Finite Binary Sequences |journal=Journal of the ACM |volume=13 |issue=4 |date=October 1966 |pages=547–569 |doi=10.1145/321356.321363|s2cid=207698337 }}</ref> | ||
Chaitin | In 1975, Chaitin defined [[Chaitin's constant]] Ω, a [[real number]] whose digits are [[normal number|equidistributed]] and which is sometimes informally described as an expression of the probability that a random program will halt. Ω has the mathematical property that it is [[Definable number|definable]], with asymptotic approximations from below (but not from above), but not [[computability theory (computation)|computable]]. | ||
Chaitin is also the originator of using [[graph coloring]] to do [[register allocation]] in [[compiling]], a process known as [[Chaitin's algorithm]].<ref>G.J. Chaitin, ''Register Allocation and Spilling via Graph Coloring'', [https://patents.google.com/patent/US4571678 US Patent 4,571,678] (1986) [cited from [http://ssw.jku.at/Teaching/PhDTheses/Hoflehner/index.html ''Register Allocation on the Intel® Itanium® Architecture''], p.155]</ref> | Chaitin is also the originator of using [[graph coloring]] to do [[register allocation]] in [[compiling]], a process known as [[Chaitin's algorithm]].<ref>G.J. Chaitin, ''Register Allocation and Spilling via Graph Coloring'', [https://patents.google.com/patent/US4571678 US Patent 4,571,678] (1986) [cited from [http://ssw.jku.at/Teaching/PhDTheses/Hoflehner/index.html ''Register Allocation on the Intel® Itanium® Architecture''], p.155]</ref> | ||
He was formerly a researcher at IBM's Thomas J. Watson Research Center in New York | He was formerly a researcher at IBM's Thomas J. Watson Research Center in New York, where he wrote more than 10 books that have been translated into about 15 languages. | ||
Afterwards Chaitin became interested in questions of [[metabiology]] and [[information theory|information-theoretic]] formalizations of the theory of [[evolution]], and he was one of the founding members of the Institute for Advanced Studies at [[Mohammed VI Polytechnic University]] in Morocco. | |||
==Other scholarly contributions== | ==Other scholarly contributions== | ||
Chaitin also writes about [[philosophy]], especially [[metaphysics]] and [[philosophy of mathematics]] (particularly about epistemological matters in mathematics). In metaphysics, Chaitin claims that [[algorithmic information theory]] is the key to solving problems in the field of [[biology]] (obtaining a formal definition of 'life', its origin and [[evolution]]) and [[neuroscience]] (the problem of [[consciousness]] and the study of the mind). | Chaitin also writes about [[philosophy]], especially [[metaphysics]] and [[philosophy of mathematics]] (particularly about epistemological matters in mathematics). In metaphysics, Chaitin claims that [[algorithmic information theory]] is the key to solving problems in the field of [[biology]] (obtaining a formal definition of 'life', its origin and [[evolution]]) and [[neuroscience]] (the problem of [[consciousness]] and the study of the mind). | ||
In recent writings, he defends a position known as [[digital physics|digital philosophy]]. In the [[epistemology]] of mathematics, he claims that his findings in [[mathematical logic]] and algorithmic information theory show there are "mathematical facts that are true for no reason, that are true by accident".<ref>{{cite arXiv|eprint = math/0303352|last1 = Chaitin|first1 = G. J.|title = From Philosophy to Program Size|year = 2003}}</ref> Chaitin proposes that mathematicians must abandon any hope of proving those mathematical facts and adopt a [[quasi-empirical]] methodology. | In recent writings, he defends a position known as [[digital physics|digital philosophy]]. In the [[epistemology]] of mathematics, he claims that his findings in [[mathematical logic]] and algorithmic information theory show there are "mathematical facts that are true for no reason, that are true by accident".<ref>{{cite arXiv|eprint = math/0303352|last1 = Chaitin|first1 = G. J.|title = From Philosophy to Program Size|year = 2003 }}</ref> Chaitin proposes that mathematicians must abandon any hope of proving those mathematical facts and adopt a [[quasi-empirical]] methodology. | ||
==Honors== | ==Honors== | ||
In 1995 he was given the degree of doctor of science ''[[honoris causa]]'' by the [[University of Maine]]. In 2002 he was given the title of honorary professor by the [[University of Buenos Aires]] in Argentina, where his parents were born and where Chaitin spent part of his youth. In 2007 he was given a [[Leibniz Medal (Wolfram Research)|Leibniz Medal]]<ref>Zenil, Hector "Leibniz medallion comes to life after 300 years" | In 1995 he was given the degree of doctor of science ''[[honoris causa]]'' by the [[University of Maine]]. In 2002 he was given the title of honorary professor by the [[University of Buenos Aires]] in Argentina, where his parents were born and where Chaitin spent part of his youth. In 2007 he was given a [[Leibniz Medal (Wolfram Research)|Leibniz Medal]]<ref>Zenil, Hector "Leibniz medallion comes to life after 300 years" | ||
[http://www.mathrix.org/liquid/archives/the-history-of-the-chaitin-leibniz-medallion ''Anima Ex Machina'', The Blog of Hector Zenil], 3 November 2007.</ref> by [[Wolfram Research]]. In 2009 he was given the degree of doctor of philosophy ''honoris causa'' by the [[National University of Córdoba]]. He was formerly a researcher at [[IBM]]'s [[Thomas J. Watson Research Center]] and a professor at the [[Federal University of Rio de Janeiro]]. | [http://www.mathrix.org/liquid/archives/the-history-of-the-chaitin-leibniz-medallion ''Anima Ex Machina'', The Blog of Hector Zenil], 3 November 2007.</ref> by [[Wolfram Research]]; the medal was designed by [[Stephen Wolfram]] and Hector Zenil, using [[Chaitin's constant | Chaitin’s number]] calculated by [[Cristian Calude]]. In 2009 he was given the degree of doctor of philosophy ''honoris causa'' by the [[National University of Córdoba]]. He was formerly a researcher at [[IBM]]'s [[Thomas J. Watson Research Center]] and a professor at the [[Federal University of Rio de Janeiro]]. | ||
==Bibliography== | ==Bibliography== | ||
*''Algorithmic Information Theory'' ([[Cambridge University Press]] 1987) ([https://web.archive.org/web/20111215170328/http://www.cs.auckland.ac.nz/~chaitin/cup.pdf online]) | |||
*''Information, Randomness & Incompleteness'' ([[World Scientific]] 1987) ([https://books.google.com/books?id=dDbE2lNiHjkC&dq=Chaitin+G.J.+%281975%29+Randomness+and+Mathematical+Proof.&pg=PA3 online]) | *''Information, Randomness & Incompleteness'' ([[World Scientific]] 1987) ([https://books.google.com/books?id=dDbE2lNiHjkC&dq=Chaitin+G.J.+%281975%29+Randomness+and+Mathematical+Proof.&pg=PA3 online]) | ||
*''Information-theoretic Incompleteness'' ([[World Scientific]] 1992) ([https://web.archive.org/web/20100514220011/http://www.cs.auckland.ac.nz/~chaitin/ps3.pdf online]) | *''Information-theoretic Incompleteness'' ([[World Scientific]] 1992) ([https://web.archive.org/web/20100514220011/http://www.cs.auckland.ac.nz/~chaitin/ps3.pdf online]) | ||
*''The Limits of Mathematics'' ([[Springer-Verlag]] 1998) ([https://www.academia.edu/99397030/The_Limits_of_Mathematics_A_Course_on_Information_Theory_and_the_Limits_of_Formal_Reasoning_Springer_Verlag_1998_ online] {{Webarchive|url=https://web.archive.org/web/20230425213929/https://www.academia.edu/99397030/The_Limits_of_Mathematics_A_Course_on_Information_Theory_and_the_Limits_of_Formal_Reasoning_Springer_Verlag_1998_ |date=25 April 2023 }}) | *''The Limits of Mathematics'' ([[Springer-Verlag]] 1998) ([https://www.academia.edu/99397030/The_Limits_of_Mathematics_A_Course_on_Information_Theory_and_the_Limits_of_Formal_Reasoning_Springer_Verlag_1998_ online] {{Webarchive|url=https://web.archive.org/web/20230425213929/https://www.academia.edu/99397030/The_Limits_of_Mathematics_A_Course_on_Information_Theory_and_the_Limits_of_Formal_Reasoning_Springer_Verlag_1998_ |date=25 April 2023 }}) | ||
*''The Unknowable'' ([[Springer-Verlag]] 1999) ([https://www.academia.edu/92235376/LISP_A_Formalism_for_Expressing_Mathematical_Algorithms_Springer_Verlag_1999_ online]) | *''The Unknowable'' ([[Springer-Verlag]] 1999) ([https://www.academia.edu/92235376/LISP_A_Formalism_for_Expressing_Mathematical_Algorithms_Springer_Verlag_1999_ online]) | ||
*''Exploring Randomness'' ([[Springer-Verlag]] 2001 | *''Exploring Randomness'' ([[Springer-Verlag]] 2001) | ||
*''Conversations with a Mathematician'' ([[Springer-Verlag]] 2002) ([https://www.academia.edu/100602330/The_Creative_Life_Conversations_with_a_Mathematician_Springer_Verlag_2002_ online]) | *''Conversations with a Mathematician'' ([[Springer-Verlag]] 2002) ([https://www.academia.edu/100602330/The_Creative_Life_Conversations_with_a_Mathematician_Springer_Verlag_2002_ online]) | ||
*''From Philosophy to Program Size'' ([http://ioc.ee/ Tallinn Cybernetics Institute] 2003) | *''From Philosophy to Program Size'' ([http://ioc.ee/ Tallinn Cybernetics Institute] 2003) ({{arXiv|math/0303352}}) | ||
*''Meta Math!: The Quest for Omega'' ([[Pantheon Books]] 2005) (reprinted in UK as ''Meta Maths: The Quest for Omega'', [[Atlantic Books]] 2006) ({{arXiv|math/0404335}}) | *''Meta Math!: The Quest for Omega'' ([[Pantheon Books]] 2005) (reprinted in UK as ''Meta Maths: The Quest for Omega'', [[Atlantic Books]] 2006) ({{arXiv|math/0404335}}) | ||
*''Thinking about Gödel & Turing'' ([[World Scientific]] 2007) ([https://www.academia.edu/100314710/Thinking_about_Gödel_and_Turing_Essays_on_Complexity_1970_2007_World_Scientific_2007_ online] {{Webarchive|url=https://web.archive.org/web/20230429215701/https://www.academia.edu/100314710/Thinking_about_G%C3%B6del_and_Turing_Essays_on_Complexity_1970_2007_World_Scientific_2007_ |date=29 April 2023 }}) | *''Thinking about Gödel & Turing'' ([[World Scientific]] 2007) ([https://www.academia.edu/100314710/Thinking_about_Gödel_and_Turing_Essays_on_Complexity_1970_2007_World_Scientific_2007_ online] {{Webarchive|url=https://web.archive.org/web/20230429215701/https://www.academia.edu/100314710/Thinking_about_G%C3%B6del_and_Turing_Essays_on_Complexity_1970_2007_World_Scientific_2007_ |date=29 April 2023 }}) | ||
*''Proving Darwin: Making Biology Mathematical'' ([[Pantheon Books]] 2012) ([https://www.academia.edu/43376660/A_mathematical_theory_of_evolution_and_biological_creativity_CDMTCS_2011_ online]) | *''Proving Darwin: Making Biology Mathematical'' ([[Pantheon Books]] 2012) ([https://www.academia.edu/43376660/A_mathematical_theory_of_evolution_and_biological_creativity_CDMTCS_2011_ online]) | ||
*'' | *''The Perfect Language'' (Jerusalem theology talk 2015) ([https://inference-review.com/article/the-perfect-language online] [https://www.worldscientific.com/doi/abs/10.1142/9781786343161_0002 online]) | ||
*''A Life in Mathematics'' (autobiographical essay 2021) ([https://researchspace.auckland.ac.nz/server/api/core/bitstreams/ffe3578c-8311-4dd1-b5e4-3ff26354f363/content online]) | |||
*''Infinity, Incompleteness, Irreducibility'' (course notes 2024) ([https://www.academia.edu/144579067/Part_I_Course_Notes_Infinity_Incompleteness_Irreducibility online]) | |||
== References == | == References == | ||
| Line 76: | Line 75: | ||
==Further reading== | ==Further reading== | ||
* {{Citation |first=Ugo |last=Pagallo |title=Introduzione alla filosofia digitale. Da Leibniz a Chaitin |language=Italian |trans-title=Introduction to Digital Philosophy: From Leibniz to Chaitin |url=http://www.giappichelli.it/home/88-348-5635-X,3485635.asp1 |publisher=G. Giappichelli Editore |year=2005 |isbn=978-88-348-5635-2 |ref=none |access-date=16 April 2008 |archive-url=https://web.archive.org/web/20110722034613/http://www.giappichelli.it/home/88-348-5635-X,3485635.asp1 |archive-date=22 July 2011 }} | * {{Citation |first=Ugo |last=Pagallo |title=Introduzione alla filosofia digitale. Da Leibniz a Chaitin |language=Italian |trans-title=Introduction to Digital Philosophy: From Leibniz to Chaitin |url=http://www.giappichelli.it/home/88-348-5635-X,3485635.asp1 |publisher=G. Giappichelli Editore |year=2005 |isbn=978-88-348-5635-2 |ref=none |access-date=16 April 2008 |archive-url=https://web.archive.org/web/20110722034613/http://www.giappichelli.it/home/88-348-5635-X,3485635.asp1 |archive-date=22 July 2011 }} | ||
* {{Citation |editor-first=Cristian S. |editor-last=Calude |title=Randomness and Complexity. From Leibniz to Chaitin |publisher=World Scientific |year=2007 |isbn=978-981-277-082-0 |ref=none}} | * {{Citation |editor-first=Cristian S. |editor-last=Calude |title=Randomness and Complexity. From Leibniz to Chaitin |publisher=World Scientific |year=2007 |isbn=978-981-277-082-0 |doi=10.1142/6577 |ref=none}} | ||
* {{Citation |editor-first=Shyam |editor-last=Wuppuluri |editor2-first=Francisco A. |editor2-last=Doria|title=Unravelling Complexity: The Life and Work of Gregory Chaitin |publisher=World Scientific |year=2020 |isbn=978-981-12-0006-9 |doi=10.1142/11270 |s2cid=198790362 }} | * {{Citation |editor-first=Shyam |editor-last=Wuppuluri |editor2-first=Francisco A. |editor2-last=Doria|title=Unravelling Complexity: The Life and Work of Gregory Chaitin |publisher=World Scientific |year=2020 |isbn=978-981-12-0006-9 |doi=10.1142/11270 |s2cid=198790362 }} | ||
* {{Citation |first=Dan |last=Gusfield |title=Proven Impossible: Elementary Proofs of Profound Impossibility from Arrow, Bell, Chaitin, Gödel, Turing and More |publisher=Cambridge University Press |year=2024 |isbn=978-1-009-34950-5 |doi=10.1017/9781009349451}} | |||
==External links== | ==External links== | ||
{{wikiquote}} | {{wikiquote}} | ||
*[https:// | |||
*[https://rocky.github.io/gjchaitin.pdf Greg Chaitin, Computer Programmer] | |||
*[https://researchspace.auckland.ac.nz/server/api/core/bitstreams/ffe3578c-8311-4dd1-b5e4-3ff26354f363/content G J Chaitin Autobiography] | |||
*[https://independent.academia.edu/VirginiaChaitin G J Chaitin Home Page from academia.edu] | |||
*[http://cs.umaine.edu/~chaitin/ G J Chaitin Home Page from UMaine.edu in the Internet Archive] {{Webarchive|url=https://web.archive.org/web/20131029184916/http://cs.umaine.edu/~chaitin/ |date=29 October 2013 }} | *[http://cs.umaine.edu/~chaitin/ G J Chaitin Home Page from UMaine.edu in the Internet Archive] {{Webarchive|url=https://web.archive.org/web/20131029184916/http://cs.umaine.edu/~chaitin/ |date=29 October 2013 }} | ||
*{{YouTube|RlYS_GiAnK8|Video of lecture on metabiology: "Life as evolving software"}} (a single mutating software organism) | |||
*{{YouTube|RlYS_GiAnK8|Video of lecture on metabiology: "Life as evolving software"}} | *{{YouTube|W0YjaOmAjF8|Video of lecture on metabiology 2.0: "Von Neumann on biology and life as evolving software”}} (a gas of software organisms and mutagens) | ||
*[http://videolectures.net/ephdcs08_chaitin_lcai/ Video of lecture on "Leibniz, complexity and incompleteness"] | *[http://videolectures.net/ephdcs08_chaitin_lcai/ Video of lecture on "Leibniz, complexity and incompleteness"] | ||
*[https://web.archive.org/web/20060510171405/http://www.dc.uba.ar/people/profesores/becher/ns.html New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas] | *[https://web.archive.org/web/20060510171405/http://www.dc.uba.ar/people/profesores/becher/ns.html New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas] | ||