программа, которая не заканчивается

[mihatel]

Существует ли программа, которая не заканчивается и не содержит бесконечного цикла, т.е. принципиально отличается от

while 0 = 0 do
begin
...
end;

Может быть есть какой-нибудь язык, диалект, архитектура или абстрактная математическая модель, на которой эта программа может быть реализована?

[General]

К примеру, такая:
while i < 3 do
begin
i:=random(2);
end;

Но она из той же оперы

[worm2]

Всё упирается в вопросы, что считать циклом и что считать программой. Например, обычно рекурсию за цикл не считают. С другой стороны, на архитектуре с конечной памятью бесконечная рекурсия невозможна: стек переполнится. С третьей стороны, есть т.н. хвостовая рекурсия, которая может на низком уровне оптимизироваться фактически в цикл, однако на верхнем уровне абстракции цикла как бы нет.

Если всякую программу, в которой возможно (количественно неограниченное) выполнение одного и того же элемента (оператора, команды, инструкции или как ещё там может это называться?) считать имеющей цикл, то очевидно, конечная программа без циклов всегда будет заканчиваться.

Если называть "бесконечным циклом" такой процесс, при котором в некоторый момент времени состояние программы (текущий оператор, содержимое памяти и т.п.) полностью идентично состоянию в некоторый предыдущий момент времени, а поведение программы полностью детерминировано её состоянием, то тоже достаточно легко показать, что на машине с конечной памятью любая программа либо остановится, либо войдёт в "бесконечный цикл". Для абстрактных архитектур с неограниченной памятью может быть конечная программа без такого "бесконечного цикла", которая не закончится:

Используется синтаксис Pascal

n := 1;
while n > 0 do
  Inc(n);

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

[Upd] General привёл другой пример реальной программы, в которой в некотором смысле нет "бесконечного цикла", тем не менее, она никогда не закончится. Но только если считать, что генератор случайных чисел Random() истинно случаен. Есть реальные архитектуры, в которых имеются истинно случайные ГСЧ. В этих архитектурах поведение программы не детерминировано её состоянием. Однако могут найтись исследователи, которые откажут таким программам в праве называться истинными программами...

[mihatel]

worm2 в сообщении #353307 писал(а):

Всё упирается в вопросы, что считать циклом и что считать программой...

Спасибо за ответ! Убедительно, но неутешительно. Грустно видеть множество зацикленных компьютеров и не хватает ума, чтобы занять их каким-нибудь полезным делом.

[В.О.]

Ответ может быть и прямо противоположным. Если под состоянием понимать не только текущее состояние ( память, оператор), но и всю предысторию (последовательность текущих состояний), то повторений не будет никогда.
Можно только стремиться к повторению.

[mihatel]

В.О. в сообщении #353940 писал(а):

Ответ может быть и прямо противоположным. Если под состоянием понимать не только текущее состояние ( память, оператор), но и всю предысторию (последовательность текущих состояний), то повторений не будет никогда.
Можно только стремиться к повторению.

С таким поворотом машина Тьюринга не справится, я думаю. Тут нужна машина времени!

[Circiter]

2mihatel
Как уже говорилось в этой теме, все зависит от того, что понимать под циклом...

Представьте себе такую программу в $\lambda$-нотации: $(\lambda\mathrm x.\mathrm x\ \mathrm x)(\lambda\mathrm x.\mathrm x\ \mathrm x)$. Это выражение неподвижно относительно $\beta$-редукции, но является редексом, поэтому и нормальной формы у него нет, что эквивалентно бесконечному циклу, при этом, однако, радикально отличающемуся от while-оператора. :)

[mihatel]

Circiter в сообщении #355171 писал(а):

2mihatel
Как уже говорилось в этой теме, все зависит от того, что понимать под циклом...

Представьте себе такую программу в $\lambda$-нотации: $(\lambda\mathrm x.\mathrm x\ \mathrm x)(\lambda\mathrm x.\mathrm x\ \mathrm x)$. Это выражение неподвижно относительно $\beta$-редукции, но является редексом, поэтому и нормальной формы у него нет, что эквивалентно бесконечному циклу, при этом, однако, радикально отличающемуся от while-оператора. :)

Спасибо! Представил. Интересно.