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

[vak]

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

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

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

Comments

[vak]

Сама постановка задачи мне всегда казалась надуманной. Если время работы программы не зависит от входных данных, то это сферический конь в вакууме. А если зависит, то о каком анализе можно говорить.

[chaource]

Время работы надо оцѣнивать какъ функцiю входныхъ данныхъ. А если входныхъ данныхъ нѣтъ, то тѣмъ лучше (значитъ, тамъ все прописано въ видѣ константъ).

Если данъ замкнутый лямбда-термъ, можно ли оцѣнить количество шаговъ редукцiи и размѣръ конечнаго значенiя?

Этотъ вопросъ эквивалентенъ поставленному въ статьѣ. Тамъ сказано, что каждый регистръ поддерживаетъ работу съ цѣлыми числами неограниченной величины. Если loop program имѣетъ входной регистръ Х и выходной регистръ F, то можно ли оцѣнить количество шаговъ и величину F какъ функцiи Х?

[vak]

Рассуждения мудрёные, но какая от них польза? К примеру, возьмём простой парсер, скажем стандартную функцию strtol(), превращающую строку в число. Что полезного теория сложности может мне про этот парсер сказать? Завершается ли он? Какая оценка времени выполнения?

[chaource]

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

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

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