Gregory Chaitin
Gregory J. Chaitin ( born 1947 in Chicago ) is an American mathematician and philosopher. His main area of work is the computability theory. He stands in the tradition of Kurt Gödel and Alan Turing, whose theorems ( incompleteness, Turing computability ) he generalized to algorithmic information theory, which is similar to the Kolmogorov complexity.
Life
Chaitin was born to Argentine immigrants from Buenos Aires. The family but moved early on to New York, where he has already attracted a young age through the book Gödel 's Proof by Ernest Nagel and James R. Newman Godel's incompleteness theorem on computability theory. ( Chaitin does this, however, on the part of Shannon's information theory to. ) He attended the Bronx High School from 1962 of Science and from 1965, the City University of New York ( CUNY ). In 1966 he went with the family to Buenos Aires, where he started as a programmer at IBM and held courses in LISP programming and meta-mathematics at the University of Buenos Aires. The early 1970s was his work information theoretic limits of formal systems ( extended published in ACM Journal 1974), an invitation to the Thomas J. Watson Research Center of IBM brought him where he is today. From 1976 to 1985 he worked as a software and hardware engineer at IBM 's RISC project. He is currently also a visiting professor in the Computer Science Department at the University of Auckland in New Zealand.
Work
His results concerning the structure of mathematical theories. Chaitin looking statements to basic computability and decidability basic mathematical theorems.
He dealt with examples of principle undecidable sentences. In such sentences, it is completely " random", whether they were true or false. However, the English term can also mean random random or random; meant here is that these rates may not be " justified ," but " it's just so ".
According to Chaitin he has proved that it is undecidable finitely many exceptions to on whether a number is Kolmogorov - reducible, ie if there is a small program that creates these numbers. So there exists no general method by which the Kolmogorov complexity could be measured.
The interpretation of Chaitin's results is controversial among some mathematicians. From him comes the Chaitinsche constant.
Chaitin has also written much on the philosophy of mathematics, in particular in the context of Gödel's incompleteness and complexity issues.
In 1995 he became an honorary doctorate from the University of Maine and received in 2002 an honorary professorship in Buenos Aires.
Writings
- Algorithmic information theory, Cambridge University Press 1987
- The Limits of Mathematics, Springer-Verlag, 1998.
- The Unknowable, Springer- Verlag, 1999.
- Exploring Randomness, Springer- Verlag, 2001.
- Conversations with a Mathematician, Springer- Verlag, 2002.
- Meta Math! , Pantheon Books 2005
- Randomness and mathematical proof, Scientific American 1975
- Randomness in Arithmetic, Scientific American 1988