LINUX.ORG.RU

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

 


0

2

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

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

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

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

★★★☆☆

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

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

anonymous ()

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

anonymous ()

а какой ЯП используете?

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

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

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

stevejobs ★★★☆☆ ()

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

subwoofer ★★★★★ ()

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

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

расскажи что за оптимизации, какие именно циклы оптимизируют и как

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

забыл конечность бесконечности:

while(forever){
    do_forever_things();
}
А true она и в африке true

minakov ★★★★★ ()

Тред про программирование или математику?

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

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

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

anonymous ()

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

Признавайся - ты взял эту тему с рсдн?

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

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

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

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

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

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

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

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

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

Тред про вещества, и к чему приводит их передоз.

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

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

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

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

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

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

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

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

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

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

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

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

subwoofer ★★★★★ ()

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

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

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

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

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

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

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

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

subwoofer ★★★★★ ()

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

Механизм Артура Гэнсона, который совершает один оборот за 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 ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.