Книга: Золотой билет

Письмо Гёделя

Письмо Гёделя

В 1956 году Курт Гёдель написал письмо Джону фон Нейману – пионеру в информатике и многих других областях науки. В письме Гёдель на немецком языке рассуждал о проблеме выполнимости и о вопросе равенства классов P и NP, только формулировал он этот вопрос в несколько иных терминах. По словам ученого, если бы мы жили в мире, в котором P = NP, то «математикам более не пришлось бы тратить время на задачи типа „да-нет“: этот труд за них выполняли бы машины <…> Впрочем, я уже перестал относить эту возможность к области несбыточного». Идеи Гёделя на пятнадцать лет опередили работы Левина и Кука.

Получил ли фон Нейман то письмо? Ответил ли он Гёделю? Мы этого не знаем; на тот момент фон Нейман уже был болен раком, и в 1957 году его не стало. О письме научное сообщество узнало лишь в конце восьмидесятых, когда за вопросом о равенстве P и NP уже прочно закрепился статус одной из центральных открытых научных проблем. Сам Гёдель умер в 1978 году; душевное расстройство, омрачившее последние годы его жизни, помешало ученому понять, что Кук в своей работе поднял тот же вопрос.

Так почему бы не назвать вопрос «проблемой Гёделя»? Почему не признать за Гёделем приоритет? Ведь он пришел к нему намного раньше, чем Кук и Левин! К сожалению, – или, возможно, к счастью, – в науке действует тот же принцип, что и в мореплавании: Христофор Колумб прославился не потому, что первым открыл Америку, а потому, что открыл ее последним. Впрочем, Гёдель тут и сам, как говорится, дал маху: не осознавая значимость поднятых в письме к фон Нейману вопросов, ученый никогда не публиковал свои идеи. Если смотреть на публикации, то первыми проблему равенства P и NP сформулировали все-таки Кук и Левин.

В 1993 году научное сообщество, отдавая дань Гёделю за его фундаментальный вклад в логику и высказанные в письме идеи, учредило премию в его честь. Премией Гёделя отмечают недавно появившиеся работы в области теоретической информатики.

Оглавление книги