Грегорі Джон Хайтін (; , , США) — аргентино-американський математик і інформатик, зробив внесок у метаматематику, спільно з Андрієм Колмогоровим вважається засновником алгоритмічної теорії інформації. Зокрема відомий своєю новою теоремою про неповноту, схожою за духом з теоремою Геделя про неповноту.
Біографія Хайтін народився в Чикаго, в сім'ї аргентинських іммігрантів з Буенос-Айреса. Незабаром Хайтіни переїхали в Нью-Йорк. Ще дитиною його привернула стаття Ернста Нагеля і Джеймса Ньюмена «Доведення Геделя», опублікована 1956 року в журналі Scientific American. Через два роки її автори випустили однойменну книгу, яку Хайтін читав у Нью-Йоркській публічній бібліотеці. 1959 року, за вказівками з розділу Amateur Scientist в Scientific American, він побудував генератор Ван де Граафа.
Хайтін здобув освіту в Bronx High School of Science і Сіті Коледжі, де він і сформулював свою теорему. 1966 року сім'я повернулась у Буенос-Айрес, де він став програмістом у IBM Argentina.
1974 року Хайтіна запросили в , де він працює донині. Від 1976 до 1985 він працював там програмним і апаратним інженером над проєктом IBM RISC.
1995 року йому присуджено ступінь доктора наук in honoris causa університету Мену, а 2002 року — звання почесного професора Університету Буенос-Айреса. Від 2000 року він також є запрошеним професором в університеті Окленда.
Наукова робота Коло наукових інтересів Хайтіна лежить в галузі теорії інформації, теорії обчислюваності, основах математики. Ранні роботи Хайтіна з алгоритмічної теорії інформації паралельні раннім роботам Колмогорова.
Хайтін увів Ω, дійсне число, цифри якого рівнорозподілені і яке іноді називають виразом ймовірності, що довільно взята програма зупиниться. Математичною властивістю Ω є те, що воно означуване, але не обчислюване.
Хайтін також займається питаннями філософії, особливо метафізикою і філософією математики, зокрема, епістемологічними проблемами математики. У метафізиці Хайтін стверджує, що алгоритмічна теорія інформації — ключ до вирішення проблем у таких галузях, як біологія (отримання формального визначення життя, його походження і еволюція) і нейробіологія (проблема свідомості і вивчення процесів мислення). Фактично, в останніх своїх працях, він відстоює позицію, відому як . В епістемології математики він заявляє, що його відкриття в математичній логіці й алгоритмічній теорії інформації показали, що існують математичні факти, істинність яких не можна пояснити ніякою теорією. «Довести» ці факти можна тільки одним способом: визнати їх аксіомами без будь-яких міркувань. Хайтін пропонує математикам облишити спроби довести ці факти і прийняти квазіемпіричну методологію.
Хайтін також є автором використання хроматичного числа для розподілу регістрів під час компіляції (див. ).
Критика Деякі філософи і логіки абсолютно не згодні з філософськими висновками, які Хайтін вивів зі своїх теоремPanu Raatikainen «Exploring Randomness and The Unknowable» Notices of the American Mathematical Society Book Review October 2001. Логік Torkel Franzén Gödel's Theorem: An Incomplete Guide to its Use and Abuse. Веллеслі, Массачусетс: , 2005. x + 172 pp. ISBN 1-56881-238-8. критикував інтерпретацію Хайтіном теореми Геделя про неповноту і сумнівне пояснення, яке дав їй Хайтін у своїх роботах.
Література Algorithmic Information Theory, (Cambridge University Press, 1987), Information, Randomness & Incompleteness, (World Scientific , 1987), Information-Theoretic Incompleteness, (World Scientific , 1992), The Limits of Mathematics, (Springer-Verlag 1998), The Unknowable, (Springer-Verlag 1999), Exploring Randomness, (Springer-Verlag 2001), Conversations with a Mathematician, (Springer-Verlag 2002), From Philosophy to Program Size, (Tallinn Cybernetics Institute 2003), Meta Math!: The Quest for Omega, (Pantheon 2005), Thinking about Gödel & Turing, (World Scientific , 2007).
Примітки
Посилання Особиста сторінка Хайтіна Список публікацій Хайтіна New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas Короткий варіант доведення Хайтіна