хартманис и машины тьюринга
Недавно в почтенном возрасте 94 лет умер ученый Юрис Хартманис, один из основателей теории сложности в современной информатике. Должен признаться, что я не знал о его существовании. Главное, за что его почитали, как я узнал например из этой заметки - это за статью 1965 года, в которой он с соавтором ввел понятие сложности алгоритма, зафиксированное как количество шагов машины Тьюринга, выполняющей данный алгоритм. Это в свою очередь привело к привычным сегодня определениям классов P, NP, самой знаменитому в информатике нерешенному вопросу P?=NP и вообще всей теории сложности, вплоть до квантовых машин Тьюринга и квантовых вычислений, популярных сегодня.
Меня это поразило, потому что немного "журденовская" ситуация получилась. Г-н Журден в пьесе Мольера с удивлением узнал, что всю жизнь говорил прозой, не зная того. У меня не было понимания того, что в вопросе определения сложности надо было что-то "устанавливать"; идея считать шаги машины Тьюринга казалась столь очевидной, что даже не приходило в голову, что кому-то это должно было придти в голову. Но тем не менее это так; и в комментариях к записи говорят немного о том, как статья Хартманиса и Стернса изменила то, как все думали в то время о более быстрых и более медленных алгоритмах, просто-таки перепахала мозги всем в этой области. А ведь могло сложиться все по-другому, например, стали бы измерять сложность через число β-редукций в вычислении лямбда-выражения, или что-то типа того...
Вот еще две блог-записи о Хартманисе, в которых в самих записях и комментариях много отзывов его учеников и коллег:
https://rjlipton.wpcomstaging.com/2022/07/29/juris-hartmanis-1928-2022/
https://scottaaronson.blog/?p=6622
Меня это поразило, потому что немного "журденовская" ситуация получилась. Г-н Журден в пьесе Мольера с удивлением узнал, что всю жизнь говорил прозой, не зная того. У меня не было понимания того, что в вопросе определения сложности надо было что-то "устанавливать"; идея считать шаги машины Тьюринга казалась столь очевидной, что даже не приходило в голову, что кому-то это должно было придти в голову. Но тем не менее это так; и в комментариях к записи говорят немного о том, как статья Хартманиса и Стернса изменила то, как все думали в то время о более быстрых и более медленных алгоритмах, просто-таки перепахала мозги всем в этой области. А ведь могло сложиться все по-другому, например, стали бы измерять сложность через число β-редукций в вычислении лямбда-выражения, или что-то типа того...
Вот еще две блог-записи о Хартманисе, в которых в самих записях и комментариях много отзывов его учеников и коллег:
https://rjlipton.wpcomstaging.com/2022/07/29/juris-hartmanis-1928-2022/
https://scottaaronson.blog/?p=6622