Хайтин, Грегори

Хайтин родился в Чикаго, в семье аргентинских иммигрантов из Буэнос-Айреса. Вскоре Хайтины переехали в Нью-Йорк. Ещё ребёнком его привлекла статья Эрнста Нагеля и Джеймса Ньюмана «Доказательство Гёделя», опубликованная в 1956 году в журнале Scientific American. Через два года её авторы выпустили одноимённую книгу, которую Хайтин читал в Нью-йоркской публичной библиотеке. В 1959 году, следуя указаниям из раздела Amateur Scientist в Scientific American, он построил генератор Ван де Граафа.

Хайтин получил образование в Bronx High School of Science^[1] и Сити-колледже, где он и сформулировал свою теорему. В 1966 году семья возвращается в Буэнос-Айрес, где он становится программистом в IBM Argentina.

В 1974 году Хайтин был приглашён в исследовательский центр IBM им. Томаса Уотсона, где он впоследствии работал^[2].

С 1976 по 1985 работал там программным и аппаратным инженером над проектом IBM RISC. В 1995 ему была присуждена степень доктора наук in honoris causa Университета Мэна. С 2000 года он также является приглашённым профессором в Университете Окленда. В 2002 году Хайтин получил звание почётного профессора Университета Буэнос-Айреса, а в 2009 году — степень почётного доктора Национального университета Кордовы.

После завершения карьеры в IBM Хайтин продолжил академическую деятельность в Федеральном университете Рио-де-Жанейро; в источнике 2011 года он указан как приглашённый профессор программы по эпистемологии и истории науки и техники.

С августа 2023 по июнь 2024 года Хайтин находился в резиденции Института перспективных исследований Университета Мохаммеда VI (IAS UM6P). В этот период он завершил рукопись Philosophical Mathematics: Infinity, Incompleteness, Irreducibility и совместно с Рафаэлем Лиожье работал над книгой-интервью The Infinite Dialogue^[3].

В профиле 2026 года Хайтин указан как профессор Федерального университета Рио-де-Жанейро^[4].

Круг научных интересов Хайтина лежит в области теории информации, теории вычислимости, основаниях математики. Ранние работы Хайтина по алгоритмической теории информации параллельны ранним работам Колмогорова.

В алгоритмической теории информации сложность строки определяется длиной кратчайшей программы, которая её порождает; строка считается алгоритмически случайной, если её нельзя существенно сжать таким описанием. Информационно-теоретическая теорема Хайтина о неполноте устанавливает предел сложности конкретной строки, превышение которого данная формальная аксиоматическая система доказать не может^[5]. В формулировке через константу Ω формальная аксиоматическая теория информационной сложности N может определить не более N + c её битов, где c — константа, зависящая от выбранного языка описания^[5].

Хайтин ввёл константу Хайтина Ω — действительное число от 0 до 1, равное вероятности того, что случайно сгенерированная программа остановится на универсальной машине Тьюринга. Его цифры равнораспределены; сама константа определима, но не вычислима и алгоритмически случайна.

Хайтин предложил концепцию метабиологии — математическую абстракцию эволюции, объединяющую алгоритмическую теорию информации и теорию вычислимости. В этой модели ДНК рассматривается как программный код, организмы — как эволюционирующие программы, а мутации — как изменения программ, сложность которых измеряется в битах алгоритмической информации^[2].

Хайтин также занимается вопросами философии, в особенности метафизикой и философией математики, в частности, эпистемологическими проблемами математики. В метафизике Хайтин утверждает, что алгоритмическая теория информации — ключ к разрешению проблем в таких областях, как биология (получение формального определения жизни, её происхождение и эволюция) и нейробиология (проблема сознания и изучение процессов мышления). Фактически, в последних своих трудах, он отстаивает позицию, известную как цифровая философия. В эпистемологии математики он заявляет, что его открытия в математической логике и алгоритмической теории информации показали, что существуют математические факты, истинность которых нельзя объяснить никакой теорией^[5]. «Доказать» эти факты можно только одним способом: признать их аксиомами без всяких рассуждений. Хайтин предлагает математикам оставить всякую надежду доказать эти факты и принять квазиэмпирическую методологию.

Хайтин также является автором использования хроматического числа (англ. graph coloring) для распределения регистров при компиляции, известного как алгоритм Хайтина.

• Algorithmic Information Theory, (Cambridge University Press, 1987),
• Information, Randomness & Incompleteness, (World Scientific, 1987),
• Information-Theoretic Incompleteness, (World Scientific, 1992^[7]),
• 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),
• Proving Darwin: Making Biology Mathematical (Pantheon Books, 2012),
• Philosophical Mathematics: Infinity, Incompleteness, Irreducibility (опубликована онлайн на Academia.edu, 2023).