Gregory John Chaitin ( / ˈ tʃ aɪ t ɪ n / CHY -tin ; * 25. Juni 1947) ist ein argentinisch - amerikanischer Mathematiker und Informatiker . Seine Arbeit war grundlegend für die Entwicklung der algorithmischen Informationstheorie und hatte großen Einfluss auf die Metamathematik . [ 2 ] [ 3 ] Er entdeckte unabhängig von Andrei Kolmogorov und Ray Solomonoff die heute als algorithmische (Kolmogorov- oder Solomonoff-Kolmogorov-Chaitin-) Komplexität bekannte Komplexität . [ 4 ]

Mathematik und Informatik

Gregory Chaitin ist Jude . Er besuchte die Bronx High School of Science und das City College of New York , wo er (noch als Teenager) die Theorie entwickelte, die zu seiner unabhängigen Entdeckung der algorithmischen Komplexität führte . [ 5 ] [ 6 ]

1975 definierte Chaitin die Chaitin-Konstante Ω, eine reelle Zahl mit gleichverteilten Ziffern , die informell oft als Ausdruck der Wahrscheinlichkeit für das Abbruchkriterium eines Zufallsprogramms beschrieben wird. Ω ist mathematisch definierbar und lässt sich asymptotisch von unten (aber nicht von oben) annähern, ist jedoch nicht berechenbar .

Chaitin ist auch der Urheber der Verwendung von Graphfärbung zur Registerzuweisung beim Kompilieren , ein Verfahren, das als Chaitins Algorithmus bekannt ist . [ 7 ]

Zuvor war er Forscher am Thomas J. Watson Research Center von IBM in New York, wo er mehr als zehn Bücher verfasste, die in etwa 15 Sprachen übersetzt wurden.

Anschließend interessierte sich Chaitin für Fragen der Metabiologie und informationstheoretische Formalisierungen der Evolutionstheorie und war eines der Gründungsmitglieder des Instituts für Höhere Studien an der Mohammed VI Polytechnic University in Marokko.

Weitere wissenschaftliche Beiträge

Chaitin schreibt auch über Philosophie , insbesondere über Metaphysik und Philosophie der Mathematik (vor allem über erkenntnistheoretische Fragen in der Mathematik). Im Bereich der Metaphysik behauptet Chaitin, dass die algorithmische Informationstheorie der Schlüssel zur Lösung von Problemen in der Biologie (der formalen Definition von „Leben“, seinem Ursprung und seiner Evolution ) und den Neurowissenschaften (dem Problem des Bewusstseins und der Erforschung des Geistes) sei.

In seinen jüngsten Schriften vertritt er die Position der digitalen Philosophie . In der Erkenntnistheorie der Mathematik behauptet er, seine Erkenntnisse in der mathematischen Logik und der algorithmischen Informationstheorie zeigten, dass es „mathematische Tatsachen gibt, die ohne Grund wahr sind, die zufällig wahr sind“ [ 8 ] . Chaitin schlägt vor, dass Mathematiker jede Hoffnung aufgeben müssen, diese mathematischen Tatsachen zu beweisen, und stattdessen eine quasi-empirische Methodik anwenden sollten .

Auszeichnungen

1995 wurde ihm von der University of Maine die Ehrendoktorwürde der Naturwissenschaften verliehen . 2002 wurde er von der Universität Buenos Aires in Argentinien, dem Geburtsort seiner Eltern und Ort seiner Jugend, zum Honorarprofessor ernannt . 2007 erhielt er von Wolfram Research die Leibniz-Medaille [ 9 ] , die von Stephen Wolfram und Hector Zenil unter Verwendung der von Cristian Calude berechneten Chaitin-Zahl entworfen wurde. 2009 wurde ihm von der Nationalen Universität Córdoba die Ehrendoktorwürde der Philosophie verliehen . Zuvor war er Forscher im Thomas J. Watson Research Center von IBM und Professor an der Bundesuniversität Rio de Janeiro .

Bibliographie

Referenzen

  1. ^ Gregory Chaitin (2007), Algorithmische Informationstheorie: „Chaitin-Forschungszeitleiste“
  2. ^ Calude, CS (2002). Information und Zufall: Eine algorithmische Perspektive . Texte zur theoretischen Informatik. Eine EATCS-Reihe. Springer-Verlag.
  3. ^ R. Downey und D. Hirschfeldt (2010), Algorithmic Randomness and Complexity , Springer-Verlag.
  4. ^ Panu Raatikainen, „Exploring Randomness and The Unknowable“ Notices of the American Mathematical Society Book Review Oktober 2001.
  5. ^ Li; Vitanyi (1997), Einführung in die Kolmogorov-Komplexität und ihre Anwendungen , Springer, S. 92, ISBN 9780387948683G. J. Chaitin hatte die Bronx High School of Science abgeschlossen und war 18 Jahre alt und Student am City College der City University of New York, als er zwei Arbeiten einreichte… In seiner zweiten Arbeit stellt Chaitin den Begriff der Kolmogorov-Komplexität vor…
  6. ^ Chaitin, GJ (Oktober 1966), „Über die Länge von Programmen zur Berechnung endlicher Binärfolgen“, Journal of the ACM , 13 (4): 547–569 , doi : 10.1145/321356.321363 , S2CID 207698337 
  7. ^ GJ Chaitin, Register Allocation and Spilling via Graph Coloring , US Patent 4,571,678 (1986) [zitiert aus Register Allocation on the Intel® Itanium® Architecture , S. 155]
  8. ^ Chaitin, GJ (2003). „From Philosophy to Program Size“. arXiv : math/0303352 .
  9. ^ Zenil, Hector "Leibniz-Medaillon erwacht nach 300 Jahren zum Leben" Anima Ex Machina , Der Blog von Hector Zenil , 3. November 2007.

Weiterführende Literatur

  • Pagallo, Ugo (2005), Einführung in die digitale Philosophie. Da Leibniz a Chaitin [ Einführung in die digitale Philosophie: Von Leibniz bis Chaitin ] (auf Italienisch), G. Giappichelli Editore, ISBN 978-88-348-5635-2archiviert vom Original am 22. Juli 2011 , abgerufen am 16. April 2008
  • Calude, Cristian S. (Hrsg.) (2007), Zufall und Komplexität. Von Leibniz bis Chaitin , World Scientific, doi : 10.1142/6577 , ISBN 978-981-277-082-0
  • Wuppuluri, Shyam; Doria, Francisco A. (Hrsg.) (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin , World Scientific, doi : 10.1142/11270 , ISBN 978-981-12-0006-9, S2CID  198790362
  • Gusfield, Dan (2024), Proven Impossible: Elementary Proofs of Profound Impossibility from Arrow, Bell, Chaitin, Gödel, Turing and More , Cambridge University Press, doi : 10.1017/9781009349451 , ISBN 978-1-009-34950-5