Лестница Шильда [неофициальное электронное издание]

46

Планета названа в честь американского математика и программиста Грегори Хайтина (1947), известного работами по теории алгоритмов. Предложил альтернативную формулировку теоремы Гёделя о неполноте. Ввел понятие константы Хайтина Ω — неформального (притом невычислимого) индикатора вероятности остановки случайно выбранной компьютерной программы. Каждая по отдельности цифра константы Хайтина вычислима, но вся константа в целом — нет. В общем случае проблема остановки средствами современной математики не ре-шается, однако применение подхода, предложенного Хайтиным, позволяет значительно упростить множество задач теории чисел и теории алгоритмов, в силу их вычислительной эквивалентности проблеме остановки. (прим. перев.)