Как проверить, завершается ли программа?

Question

Есть ли общее правило, которое можно использовать для определения этого? Например:

int i = 10;
while (i > 1 ) {
  if (i%2 == 0) i = i/2;
  else i = 3*i - 1;
}

Answer 1

Это проблема остановки . Не существует алгоритма, способного выполнять то, что вы просите.

В частности, если бы существовал такой алгоритм, то гипотеза Коллатца , относящаяся к функции в вашем вопросе, была бы тривиальной (или, по крайней мере, намного проще).

Answer 2

В общем "нет".Как и все остальные, с вашим конкретным примером можно доказать, что он не завершается, поскольку i только меньше, если i четное (или если i неположительно и нечетно, но с учетом начальнойусловия, которых никогда не будет).Наименьшее положительное четное число равно 2, затем оно превращается в 1 для следующей итерации, где оно затем превращается в 2.

Интересно, что вы не проверяете гипотезу Коллатца, так как выполняете итерацию "делить пополам, если четное, 3 * n-1, если нечетное ", и гипотеза Коллатца повторяет" вдвое, если четное, 3 * n + 1, если нечетное ".Я не могу найти эту последовательность обсуждений с быстрым поиском.

Answer 3

Возможно, вы имеете в виду проблему остановки. Короче говоря, нет общего способа определить, остановится ли программа. Проверьте эту статью .

Answer 4

Есть несколько методов для анализа завершения , который может доказать, остановится ли программа. Это не всегда возможно в языках программирования с полным набором Тьюринга, но есть несколько полных функциональных языков программирования , которые ограничены программами, которые могут быть остановлены.