LINUX.ORG.RU

бесконечный цикл за конечное время

 


0

2

недавно заметил этот вопрос в интернетах

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

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

а что вы думаете?

★★★★☆

Последнее исправление: cetjs2 (всего исправлений: 2)

возможно ... при наличии бесконечных ресурсов

ящитаю перенос множителей сути не меняет

anonymous
()

Для этого нужен просто правильный процессор.

anonymous
()
Ответ на: комментарий от anonymous

неважно, бери любой.

если сторонник идеи, что великие произведения искусства делаются только в условиях крайней ограниченности ресурсов, то предлагаю Java

stevejobs ★★★★☆
() автор топика

Ээээ, а практическая цель какая? Я что-то с трудом представляют зачем бесконечное сводить к конечному в рамках программирования.

Pinkbyte ★★★★★
()
$ time while [ 1 ]; do echo 1; break; done
1

real	0m0.000s
user	0m0.000s
sys	0m0.000s
anTaRes ★★★★
()

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

anonymous
()
Ответ на: комментарий от Deleted

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

stevejobs ★★★★☆
() автор топика
Ответ на: комментарий от stevejobs

из реальных случаев это только queue-loop процессы, которые бесконечно занимаются обработкой привалившихся сообщений, но к ним твой пятничный посыл не применим

Deleted
()
Ответ на: комментарий от DarkEld3r

рсдн дал идею, а так весь гуголь по запросу «infinite loop in finite time»

сегодня упоровшись наглухо

щито вы имеете против упоротости? Я постоянно употребляю вещества, например перед походом в общество, на вечеринку. Общение с женщинами вытягивает силы, и потом когда доходишь до момента когда надо уже эээ что-то делать, сил-то и не осталось. Поэтому надо основательно употребить перед выходом! А сейчас как раз пятница, время культурного отдыха вечером.

stevejobs ★★★★☆
() автор топика
Ответ на: комментарий от iVS

— Мы с друзьями выпили Фанты и выполнили бесконечный цикл за 15 секунд.

Deleted
()
Ответ на: комментарий от stevejobs

Так там как бы не бесконечный цикл(по идее). Там цикл на овердофига итераций, но он конечен. А бесконечный, в моём понимании, это while true без всяких условий на break внутри.

Pinkbyte ★★★★★
()
Последнее исправление: Pinkbyte (всего исправлений: 1)
Ответ на: комментарий от Deleted

ну допустим есть какой-то бесконечный queue-loop процесс, но по его исходнику можно аналитически доказать, что конечным результатом обработки будет эээ увеличение какой-то переменной на 2.

что ты меня спрашиваешь, это я тебя спрашиваю, кто тут ТС и задает вопросы?!

stevejobs ★★★★☆
() автор топика
Ответ на: комментарий от stevejobs

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

т.е. аналитически спрогнозировать зависание

Deleted
()

Ты тоже прочитал что последняя модель суперкомпьтера Cray настолько совершенна, что может выполнить бесконечный цикл всего за шесть секунд?

sin_a ★★★★★
()
Ответ на: комментарий от stevejobs

Делаешь результатом ленивый поток и оперируешь потоками вытаскивая сколько нужно.. Ну и все ряды/рекурентные соотношения которые аналитически вычисляются так же.

qnikst ★★★★★
()
Ответ на: комментарий от Deleted

Ну вот допустим у нас есть некий алгоритм, записанный.. на C++. Пусть мы даже знаем, что вот этот алгоритм - бесконечный. Теперь, как именно аналитически доказать, что этот алгоритм принадлежит к классу «могущих быть сведенными к выполнимому за конечное время»? И более жестко, как это определить автоматически (чтобы можно было встроить в компилятор)?

stevejobs ★★★★☆
() автор топика
Ответ на: комментарий от stevejobs

Пусть мы даже знаем, что вот этот алгоритм - бесконечный.

вот пример в студию, только не надо всякие там брутфорсы хешей - они не бесконечные

Deleted
()
Ответ на: комментарий от Deleted

предел числовой последовательности?

stevejobs ★★★★☆
() автор топика

Механический пример бесконечного цикла (тут):

Механизм Артура Гэнсона, который совершает один оборот за 2.3 триллиона лет

Весь фокус машины Артура Гэнсона заключается в том, что каждый из его 12 механизмов имеет передаточный коэффициент частоты вращения 1 к 50.

А у самой машины, равно как и у куска бетона, в который вмонтирована ось последнего механизма, нет никаких шансов дожить до того момента, когда поворот вала начнет разрушать бетонный блок. Неумолимое время, коррозия металла и другие неблагоприятные факторы разрушат эту машину гораздо раньше, чем она сможет завершить один полный оборот.

т.е. любой цикл закончится тогда, когда «сдохнет» система выполняющая этот цикл

anTaRes ★★★★
()
Ответ на: комментарий от stevejobs

Минимальное действие - один такт, то есть отнимает конечное время. Умножаем на количество итераций, получаем, что нельзя.

/thread

anonymous
()

про «что это делает в development» уже вопрошали?

ananas ★★★★★
()

Где-то в 90х годах, когда вышел Pentium, ходила байка: «теперь процессоры intel бесконечный цикл выполняют за секунды».
Впрочем эта шутка была и про девайсы от Cray.

andreyu ★★★★★
()

некоторые бесконечные циклы возможно выполнить за конечное время при наличии бесконечных ресурсов.

какой же бред ты читаешь, это просто п*ц. А кто-то еще говорит, что я упорот.

J-yes-sir
()

бесконечные циклы возможно выполнить за конечное время

какой-нибудь loop (проснулся-поработал-уснул) в ожидании события (побудки)

Deleted
()

некоторые бесконечные циклы возможно выполнить за конечное время при наличии бесконечных ресурсов.

Их даже на конечных ресурсах выполнить реально, но не на жабе.

VAR
Z: longint=0;
LABEL
1,2;
BEGIN
1:
inc(Z);
Writeln('Цикл выполняю, тролля Джобса развлекаю. ',Z);
if Z>1000000 then goto 2;
goto 1;
2:
END.

Napilnik ★★★★★
()
Ответ на: комментарий от Napilnik

Или так, с прыжком в начало

VAR
Z: longint=0;
LABEL
1,2,3;
BEGIN
3:
if Z<100000 then goto 1;
goto 2;
1:
inc(Z);
Writeln('Цикл выполняю, тролля Джобса развлекаю. ',Z);
if Z>1000000 then goto 3;
goto 1;
2:
END.
Пластичность кода просто зашкаливает.

Napilnik ★★★★★
()
Последнее исправление: Napilnik (всего исправлений: 1)

«Мы все знаем, что Linux — это круто… он выполняет бесконечные циклы за 5 секунд» (c) Линус Торвальдс

Не в тему и на правах Петросяна, но что поделать.

Ceiling_QB ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.