Ритчи и сложность

[vak]

Хотите глянуть, чем занимался молодой Деннис Ритчи до того, как Кен Томпсон увлёк его игрой в Space Travel на PDP-7?

Статья Альберта Мейера и Денниса Ритчи "The complexity of loop programs" (PDF)

А сама игра вот тут: github.com/mohd-akram/st

Comments

[chaource]

Вотъ хотѣлось бы имѣть алгоритмъ, который бы умѣлъ это оцѣнивать болѣе разумно, чѣмъ въ этой статьѣ.

Если переписать strtol() какъ "loop program", а это, кажется, можно - закодировать строку хотя бы какъ ASCII однимъ большимъ цѣлымъ числомъ, - то strtol() будетъ эквивалентна какой-то loop program, и соотвѣтственно какому-то замкнутому типизированному лямбда-терму въ System F. И это уже хорошо бы попытаться какъ-то оцѣнить, хотя бы количество шаговъ редукцiи.

Есть на эту тему изслѣдованiя, - найденъ классъ рекурсивныхъ программъ (кажется, нѣсколько болѣе широкiй классъ, чѣмъ "loop programs"), для которыхъ можно синтаксически гарантировать завершенiе рекурсiи. https://en.wikipedia.org/wiki/Walther_recursion