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