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

S>Поздравляю, вы напоролись на контр-интуитивное поведение бесконечностей.
S>Все доказательства проблемы останова неявно содержат в себе предположение о том, что как программа, так и её состояние, никак не ограничены по размеру.

Так, стоп. А причем здесь вообще бесконечности?
Если программа конечного размера и она завершается, она завершается спустя конечное время.
Для заданного начального размера программ существует такое число M, что все программы, если они завершаются, то завершаются за меньшее число шагов.

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

S>Поздравляю, вы напоролись на контр-интуитивное поведение бесконечностей.
S>Все доказательства проблемы останова неявно содержат в себе предположение о том, что как программа, так и её состояние, никак не ограничены по размеру.

Так, стоп. А причем здесь вообще бесконечности?
Если программа конечного размера и она завершается, она завершается спустя конечное время.
Для заданного начального размера программ существует такое число M, что все программы, если они завершаются, то завершаются за меньшее число шагов.

Соответственно, анализатор, который тупо выполняет ее M шагов и является корректным анализатором.
Другой вопрос, как узнать это число M, но оно существует, а значит и существует соответствующая программа-анализатор.