Здравствуйте, vdimas, Вы писали:

V>Похоже, ты уже споришь сам с собой. Я же не с этим спорил, а с тем, что в практическом плане это нам ничего не даёт.
Ничего не даёт использование Анализатора вообще или конкретного описанного в доказательстве алгоритма (назовем его "наивным")?
Если наивного, то кто ещё спорит сам с собой =)
Если вообще, то есть практическое применение: http://rsdn.ru/forum/philosophy/6186702.1

Автор: kochetkov.vladimir
Дата: 18.09.15

V>Я и не обсуждал эту проблему. Я демонстрировал, что твой Анализатор не работает лучше, чем сценарий непосредственного запуска самой программы. Именно поэтому предложил покопаться в альтернативном направлении.
А я могу продемонстрировать, что это принципиально разные вещи.
Возьмём программу на питоне:

while True:
  pass
print("Done")

Даже наивный Анализатор завершается мгновенно, а программа не завершается.

К>Она тоже будет работать дольше, чем время жизни вселенной. Но люди как-то поняли, что она останавливается.
V>Не как-то, а через упомянутую дедукцию. Были найдены и доказаны св-ва алгоритма для N =0, 1, ... и были выражены св-ва алгоритма для любого N через св-ва алгоритма для (N-1).
К>Наверное, спутал с индукцией? =)
V>Почему спутал? Индукцией является умозрительный вывод (человеком) характеристик алгоритма от i = 0, 1.. до произвольного N, в процессе же работы символьного анализатора происходит обратное — именно дедукция.
Ты потерял контекст, мы и говорили о человеке. Аккерман опубликовал свою функцию в начале 20-го века.

V>Я давал оценки времени этого "всегда завершается" для небольшой разрядности и небольшого (по современным меркам) пространства состояний — Вселенная успеет миллиарды миллиардов раз по кругу схлопнуться в ЧД и снова взорваться.
V>Т.е., в смысле здравого материализма — нет ровно никакой разницы.
Для программы выше ты не успеешь подумать о вселенной, а Анализатор уже завершится.