Грегори Джон Чайтин ( / ˈ tʃ aɪ t ɪ n / CHY -tin ; родился 25 июня 1947 года) — аргентинско - американский математик и учёный-компьютерщик . Начиная с конца 1960-х годов, Чайтин внёс вклад в алгоритмическую теорию информации и метаматематику , в частности, в компьютерно-теоретический результат, эквивалентный теореме Гёделя о неполноте . [2] Он считается одним из основателей того, что сегодня известно как алгоритмическая (Соломонова–Колмогорова–Чайтина, Колмогорова или программного размера) сложность вместе с Андреем Колмогоровым и Рэем Соломоновым . Наряду с работами, например, Соломонова , Колмогорова , Мартина-Лёфа и Леонида Левина , алгоритмическая теория информации стала основополагающей частью теоретической информатики , теории информации и математической логики . [3] [4] Это распространенный предмет в нескольких учебных программах по информатике. Помимо ученых-компьютерщиков, работа Хайтина привлекает внимание многих философов и математиков к фундаментальным проблемам математического творчества и цифровой философии.
Грегори Хайтин — еврей , он учился в Высшей школе наук в Бронксе и Городском колледже Нью-Йорка , где он (еще будучи подростком) разработал теорию, которая привела его к независимому открытию алгоритмической сложности . [5] [6]
Хайтин определил константу Хайтина Ω — действительное число , цифры которого равномерно распределены и которое иногда неформально описывается как выражение вероятности остановки случайной программы. Ω обладает математическим свойством, заключающимся в том, что оно определимо с асимптотическими приближениями снизу (но не сверху), но не вычислимо .
Чайтин также является создателем использования раскраски графов для распределения регистров при компиляции , процесса, известного как алгоритм Чайтина . [7]
Ранее он был исследователем в исследовательском центре IBM Thomas J. Watson в Нью-Йорке. Он написал более 10 книг, которые были переведены примерно на 15 языков. Сегодня он интересуется вопросами метабиологии и информационно-теоретических формализаций теории эволюции и является членом Института перспективных исследований при Политехническом университете Мохаммеда VI .
Хайтин также пишет о философии , особенно метафизике и философии математики (в частности, о эпистемологических вопросах в математике). В метафизике Хайтин утверждает, что алгоритмическая теория информации является ключом к решению проблем в области биологии (получение формального определения «жизни», ее происхождения и эволюции ) и нейронауки (проблема сознания и изучение разума).
В своих недавних работах он отстаивает позицию, известную как цифровая философия . В эпистемологии математики он утверждает, что его открытия в математической логике и алгоритмической теории информации показывают, что существуют «математические факты, которые истинны без причины, которые истинны случайно». [8] Хайтин предлагает математикам отказаться от любой надежды доказать эти математические факты и принять квазиэмпирическую методологию.
В 1995 году ему была присвоена степень доктора наук honoris causa Университетом штата Мэн . В 2002 году ему было присвоено звание почетного профессора Университетом Буэнос-Айреса в Аргентине, где родились его родители и где Хайтин провел часть своей юности. В 2007 году он был награжден медалью Лейбница [9] компанией Wolfram Research . В 2009 году ему была присвоена степень доктора философии honoris causa Национальным университетом Кордовы . Ранее он был исследователем в Исследовательском центре Томаса Дж. Уотсона IBM и профессором Федерального университета Рио-де-Жанейро .
Некоторые философы и логики не согласны с философскими выводами, которые Хайтин сделал из своих теорем, связанных с тем, что Хайтин считает своего рода фундаментальной арифметической случайностью. [10] Логик Торкель Францен раскритиковал интерпретацию Хайтином теоремы Гёделя о неполноте и предполагаемое объяснение этого, которое представляет работа Хайтина. [11]
Г. Дж. Чайтин окончил Высшую школу естественных наук в Бронксе и был 18-летним студентом бакалавриата в Городском колледже Городского университета Нью-Йорка, когда он представил две статьи.... В своей [второй] статье Чайтин выдвигает понятие колмогоровской сложности....
