2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 программа, которая не заканчивается
Сообщение17.09.2010, 09:14 


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

while 0 = 0 do
begin
...
end;

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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение17.09.2010, 10:31 
Аватара пользователя


17/05/08
358
Анк-Морпорк
К примеру, такая:
while i < 3 do
begin
i:=random(2);
end;

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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение17.09.2010, 10:45 
Заслуженный участник
Аватара пользователя


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

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

Если называть "бесконечным циклом" такой процесс, при котором в некоторый момент времени состояние программы (текущий оператор, содержимое памяти и т.п.) полностью идентично состоянию в некоторый предыдущий момент времени, а поведение программы полностью детерминировано её состоянием, то тоже достаточно легко показать, что на машине с конечной памятью любая программа либо остановится, либо войдёт в "бесконечный цикл". Для абстрактных архитектур с неограниченной памятью может быть конечная программа без такого "бесконечного цикла", которая не закончится:
Используется синтаксис Pascal
n := 1;
while n > 0 do
  Inc(n);
Если здесь допустить, что n может принимать любые целые значения (никаких ограничений), то такая абстрактная программа не закончится никогда, тем не менее, состояние программы никогда не повторится (n будет каждый раз разным).

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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение17.09.2010, 13:42 


17/09/10
94
worm2 в сообщении #353307 писал(а):
Всё упирается в вопросы, что считать циклом и что считать программой...


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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение19.09.2010, 10:51 


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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение20.09.2010, 08:25 


17/09/10
94
В.О. в сообщении #353940 писал(а):
Ответ может быть и прямо противоположным. Если под состоянием понимать не только текущее состояние ( память, оператор), но и всю предысторию (последовательность текущих состояний), то повторений не будет никогда.
Можно только стремиться к повторению.


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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение22.09.2010, 18:50 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: программа, которая не заканчивается
Сообщение24.09.2010, 13:43 


17/09/10
94
Circiter в сообщении #355171 писал(а):
2mihatel
Как уже говорилось в этой теме, все зависит от того, что понимать под циклом...

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group