хартманис и машины тьюринга

Недавно в почтенном возрасте 94 лет умер ученый Юрис Хартманис, один из основателей теории сложности в современной информатике. Должен признаться, что я не знал о его существовании. Главное, за что его почитали, как я узнал например из этой заметки - это за статью 1965 года, в которой он с соавтором ввел понятие сложности алгоритма, зафиксированное как количество шагов машины Тьюринга, выполняющей данный алгоритм. Это в свою очередь привело к привычным сегодня определениям классов P, NP, самой знаменитому в информатике нерешенному вопросу P?=NP и вообще всей теории сложности, вплоть до квантовых машин Тьюринга и квантовых вычислений, популярных сегодня.

Меня это поразило, потому что немного "журденовская" ситуация получилась. Г-н Журден в пьесе Мольера с удивлением узнал, что всю жизнь говорил прозой, не зная того. У меня не было понимания того, что в вопросе определения сложности надо было что-то "устанавливать"; идея считать шаги машины Тьюринга казалась столь очевидной, что даже не приходило в голову, что кому-то это должно было придти в голову. Но тем не менее это так; и в комментариях к записи говорят немного о том, как статья Хартманиса и Стернса изменила то, как все думали в то время о более быстрых и более медленных алгоритмах, просто-таки перепахала мозги всем в этой области. А ведь могло сложиться все по-другому, например, стали бы измерять сложность через число β-редукций в вычислении лямбда-выражения, или что-то типа того...

Вот еще две блог-записи о Хартманисе, в которых в самих записях и комментариях много отзывов его учеников и коллег:

https://rjlipton.wpcomstaging.com/2022/07/29/juris-hartmanis-1928-2022/
https://scottaaronson.blog/?p=6622

государство тель-авив

Если ты в Израиле, то как распознать, ты находишься в Тель-Авиве, или в остальном Израиле?

- когда заказываешь капучино в кафе, кассирша специально переспрашивает: "молоко обычное?"

(словно не верит, что такие еще остались вообще)
(случилось со мной только что, да)
(предлагайте еще критерии! Ты знаешь, что ты в Тель-Авиве, если...?)