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

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

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

Здравствуйте, мыщъх, Вы писали:

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

Ложки нет. И циклов нет. Ничего нет.

Здравствуйте, мыщъх, Вы писали:

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

Банан велик, но кожура еще больше ©
Завязывай уже.

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

раскрытие неопределенности, правило Лопиталя

Здравствуйте, мыщъх, Вы писали:


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

А компилятор может соптимизировать

Здравствуйте, мыщъх, Вы писали:

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

А что тут думать? Вот пример:

T s = 0;
for (T k = 1; /* бесконечный цикл как в матане */; ++k)
{
    s += k / pow(2, k);
}
std::cout << s << std::endl;

здесь T — это некоторый тип для точного представления рациональных чисел. Нетрудно видеть, что s будет в точности равняться 2 (если определить бесконечную сумму так, как это делается в математическом анализе). Более того, чтобы это увидеть, достаточно конечного времени (зависит от человека / системы символьной математики) и ресурсов (листочек бумаги / несколько сотен мегабайт RAM и пара миллионов тактов CPU). Пример здесь: wolfram alpha

Здравствуйте, __kot3, Вы писали:

__>Здравствуйте, мыщъх, Вы писали:

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

__>А что тут думать? Вот пример:

__>

__>T s = 0;
__>for (T k = 1; /* бесконечный цикл как в матане */; ++k)
__>{
__>    s += k / pow(2, k);
__>}
__>std::cout << s << std::endl;
__>

__>здесь T — это некоторый тип для точного представления рациональных чисел. Нетрудно видеть, что s будет в точности равняться 2 (если определить бесконечную сумму так, как это делается в математическом анализе). Более того, чтобы это увидеть, достаточно конечного времени (зависит от человека / системы символьной математики) и ресурсов (листочек бумаги / несколько сотен мегабайт RAM и пара миллионов тактов CPU). Пример здесь: wolfram alpha
Ну, как я это понимаю, мы переписываем этот цикл на два:

T s = 0;
for(T k1 = 1; k1<K0; ++k1)
{
  s += k1 / pow(2, k1);
}
for(T k2 = K0; ; ++k2)
{
  s += 0; // т.к. k2/pow(2, k1) < epsilon для любого k2>=K0.
}
std::cout << s << std::endl;

А после этого уже компилятор оптимизирует "прочь" цикл №2 как не имеющий побочных эффектов.

Здравствуйте, мыщъх, Вы писали:

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

Если только решить эту задачу в аналитическом виде да ввести в программу готовую формулу.

Здравствуйте, Sinclair, Вы писали:

S>Ну, как я это понимаю, мы переписываем этот цикл на два:
S>

S>T s = 0;
S>for(T k1 = 1; k1<K0; ++k1)
S>{
S>  s += k1 / pow(2, k1);
S>}
S>for(T k2 = K0; ; ++k2)
S>{
S>  s += 0; // т.к. k2/pow(2, k1) < epsilon для любого k2>=K0.
S>}
S>std::cout << s << std::endl;
S>

S>А после этого уже компилятор оптимизирует "прочь" цикл №2 как не имеющий побочных эффектов.

Если здесь — "k2/pow(2, k1)" — нет опечатки (действительно стоит k1, а не k2) — то это неверно (т.к. k1 фиксировано), если опечатка есть — то это тоже неверно, т.к. суммы 1/k (k = 1..inf) не существует. Как "оптимизировать" подобные циклы — есть куча статей в интернете, по теме "symbolical mathematics".

Здравствуйте, __kot3, Вы писали:
S>>А после этого уже компилятор оптимизирует "прочь" цикл №2 как не имеющий побочных эффектов.

__>Если здесь — "k2/pow(2, k1)" — нет опечатки (действительно стоит k1, а не k2) — то это неверно (т.к. k1 фиксировано),
опечатка.

__>если опечатка есть — то это тоже неверно, т.к. суммы 1/k (k = 1..inf) не существует.
Я не очень понимаю, как вы получили 1/k из k/pow(2, k).
__>Как "оптимизировать" подобные циклы — есть куча статей в интернете, по теме "symbolical mathematics".
Детали оптимизации сильно зависят от мелочей.
Скажем, сумма ряда 1/k символической оптимизации не поддаётся. А вот если речь идёт об арифметике даблов, то начиная с конкретного K0 мы получаем при делении floating underflow и дальнейшее суммирование бессмысленно.

Здравствуйте, мыщъх, Вы писали:

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

Бесконечный цикл может быть двух родов. Это либо алгоритм вообще без допускающих состояний (т.е. всевозможные эквиваленты while(true) {}), либо с допускающими состояниями, но заведомая недостижимость которых неразрешима без его запуска на конкретных данных в результате которого, в случае их недостижимости, и возникает бесконечный цикл. И тут приходим к проблеме останова, разрешимой на данный момент только для алгоритмов, эквивалентных КА, стековомым ДКА или МТ{2,1}{1,2}{2,2}{2,3}{3,2}. Т.е. мы не можем доказать или опровергнуть выполнение того или иного алгоритма на произвольных данных за конечное время, если только не начнем играться с определением алгоритма (см. ниже).

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

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

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

Здравствуйте, мыщъх, Вы писали:

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

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

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

Здравствуйте, мыщъх, Вы писали:
М>некоторые бесконечные циклы возможно выполнить за конечное время при наличии бесконечных ресурсов.
М>а что вы думаете?

ИМХО, в случае, если каждая итерация цикла выполняется за конечное время и результаты итерации не зависят от результатов предыдущей итерации, то, имея бесконечное количество потоков, можно выполнить цикл за конечное время.

Здравствуйте, quentum, Вы писали:

Q>ИМХО, в случае, если каждая итерация цикла выполняется за конечное время и результаты итерации не зависят от результатов предыдущей итерации, то, имея бесконечное количество потоков, можно выполнить цикл за конечное время.

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

Здравствуйте, мыщъх, Вы писали:

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

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

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

Здравствуйте, fin_81, Вы писали:

_>Надо сперва дать определение цикла, времени, и бесконечности в рамках одной теории

Цикл — повторяющаяся последовательность смены состояний МТ. Время, необходимое для выполнения МТ одной атомарной операции (чтение с ленты -> переход между состояниями -> перемещение головки -> запись на ленту) — единица времени. Поскольку МТ и основные, связанные с ней теоремы, сформулированы в рамках ZFC, то вопрос определения бесконечности как бы не стоит

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Цикл — повторяющаяся последовательность смены состояний МТ. Время, необходимое для выполнения МТ одной атомарной операции (чтение с ленты -> переход между состояниями -> перемещение головки -> запись на ленту) — единица времени. Поскольку МТ и основные, связанные с ней теоремы, сформулированы в рамках ZFC, то вопрос определения бесконечности как бы не стоит

Хочешь сказать, что МТ может легко определить конечный цикл и бесконечный цикл за конечное время (количество атомарных операций)?
В теории множеств бесконечность — это характеристика множества и не является объектом множества.
Определение цикла можно дать в терминах МТ (вроде). А вот как определить бесконечность в терминах МТ?

Здравствуйте, fin_81, Вы писали:

_>Хочешь сказать, что МТ может легко определить конечный цикл и бесконечный цикл за конечное время (количество атомарных операций)?

МТ этого не может. Я хочу сказать, что МТ — и есть то, что реализует наш потенциальный цикл.

_>Определение цикла можно дать в терминах МТ (вроде). А вот как определить бесконечность в терминах МТ?

Период времени "в терминах МТ" есть упорядоченное множество всех конфигураций МТ (состояние + текущий символ на ленте + положение головки), имеющих место в процессе вычисления на конкретных данных. Соответственно, бесконечный период времени -есть бесконечное упорядоченное множество всех конфигураций МТ ... и далее по тексту.

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Период времени "в терминах МТ" есть упорядоченное множество всех конфигураций МТ (состояние + текущий символ на ленте + положение головки), имеющих место в процессе вычисления на конкретных данных. Соответственно, бесконечный период времени -есть бесконечное упорядоченное множество всех конфигураций МТ ... и далее по тексту.

И как определить это бесконечное упорядоченное множество, если мы даже не можем определить конечность или бесконечность алгоритма в общем случае?
Чтобы определить бесконечность нам надо сперва дойти до бесконечности.

Здравствуйте, kochetkov.vladimir, Вы писали:
KV>В этом случае количество потоков должно быть строго равным количеству итераций (иначе получаем неопределенное время выполнения), а количество итераций до выполнения алгоритма является неизвестной для нас величиной в соответствии с теоремой останова.

С одной стороны, я с вами согласен. Но, с другой стороны, мы имеем бесконечное множество итераций (пусть в упрощенном виде оно счетное) и бесконечное счетное множество потоков. Тогда каждому потоку за номером i мы можем назначить i-ую итерацию. Это подход для создания неопределенности [бесконечность/бесконечность]. В принципе, можно использовать другой подход [0 * бесконечность], это будет своеобразный программный дзен: бесконечное количество итераций, время выполнения которых стремится к нулю.
Тем не менее, очень интересно взглянуть на статьи, о которых говорил мыщъх.

Здравствуйте, мыщъх, Вы писали:

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

Здравствуйте, мыщъх, Вы писали:

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

И, кстати, если бы я получил посылку от Джа, то задумался бы скорее о выполнении конечного цикла за бесконечное время

Здравствуйте, quentum, Вы писали:

Q>Тем не менее, очень интересно взглянуть на статьи, о которых говорил мыщъх.

Одна из наиболее известных на эту тему: http://arxiv.org/pdf/math/9808093.pdf

Здравствуйте, fin_81, Вы писали:

_>не можем определить конечность или бесконечность алгоритма в общем случае?

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

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Мы не можем _разрешить_ бесконечность его выполнения не выполнив его. Дать же определение бесконечному циклу в терминах теории множеств нам это совершенно не мешает.

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

Бывают ли бесконечные алгоритмы?

Здравствуйте, Sinclair, Вы писали:

S>Я не очень понимаю, как вы получили 1/k из k/pow(2, k).

Я привел пример того, что даже если k-й член ряда — бесконечно мал, это не гарантирует его сходимость

S>Скажем, сумма ряда 1/k символической оптимизации не поддаётся. А вот если речь идёт об арифметике даблов, то начиная с конкретного K0 мы получаем при делении floating underflow и дальнейшее суммирование бессмысленно.

Это проблема даблов. Гармонический ряд ведет себя как логарифм (есть даже формула которая позволяет выразить его частичную сумму как логарифм n + константа).

Здравствуйте, __kot3, Вы писали:
__>Я привел пример того, что даже если k-й член ряда — бесконечно мал, это не гарантирует его сходимость
Это в символьной математике. А в математике даблов (которой оперирует большинство промышленых языков программирования) никаких бесконечно малых нет.

S>>Скажем, сумма ряда 1/k символической оптимизации не поддаётся. А вот если речь идёт об арифметике даблов, то начиная с конкретного K0 мы получаем при делении floating underflow и дальнейшее суммирование бессмысленно.

__>Это проблема даблов. Гармонический ряд ведет себя как логарифм (есть даже формула которая позволяет выразить его частичную сумму как логарифм n + константа).
Спасибо, я в курсе, как себя ведёт гармонический ряд — матан мне преподавали

Здравствуйте, fin_81, Вы писали:

_>Твое определение бесконечного по времени цикла требует того чтобы цикл априори был бесконечным, иначе это будет определение конечного цикла
Простите, это наукообразная чушь.
Определение бесконечного цикла не требует никакой "априорности". Это если под словом "определение" имеется в виду definition, а не detection.
Определение — очень простое: если для любого целого N на итерации номер N цикл всё ещё не закончился остановом, то это — бесконечный цикл.
_>Бывают ли бесконечные алгоритмы?

10 GOTO 10

Здравствуйте, Sinclair, Вы писали:

_>>Твое определение бесконечного по времени цикла требует того чтобы цикл априори был бесконечным, иначе это будет определение конечного цикла
S>Простите, это наукообразная чушь.
Не эксперт в этой области и просто хочу понять. И у меня есть подозрения, что кто-то что-то не договаривает, а по моему мировоззрению, неполная информация есть ложь.


S>Определение бесконечного цикла не требует никакой "априорности". Это если под словом "определение" имеется в виду definition, а не detection.
S>Определение — очень простое: если для любого целого N на итерации номер N цикл всё ещё не закончился остановом, то это — бесконечный цикл.

Что такое целое число в терминах МТ? Чем отличается дефинишн конечного алгоритма от детекшн в МТ? Кажется у этой проблемы есть общеизвестное название?

_>>Бывают ли бесконечные алгоритмы?

S>
S>

S>10 GOTO 10
S>

Это _алгоритм_ в какой-то теории? Или неизвестно что?
Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?

Здравствуйте, Sinclair, Вы писали:

S>Это в символьной математике. А в математике даблов (которой оперирует большинство промышленых языков программирования) никаких бесконечно малых нет.

Это лишь означает, что в математике даблов нельзя посчитать частичную сумму более чем 10^16 членов этого ряда. Если нужно суммировать меньшее количество, то думаю все получится, если начинать суммировать с конца.

Здравствуйте, fin_81, Вы писали:

_>Что такое целое число в терминах МТ?
То же самое, что и в обычной алгебре.

_>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
Всем.

_>Кажется у этой проблемы есть общеизвестное название?
Да, halting problem, она же — проблема останова.
_>Это _алгоритм_ в какой-то теории? Или неизвестно что?
_>Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?
Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
Ну так halting problem как раз в том, чтобы понять, глядя на "вычислительный метод" (в терминологии Кнута), является ли он алгоритмом или нет.
Тьюринг доказал, что невозможно построить алгоритм, который бы с уверенностью определял, завершится ли произвольная МТ за конечное количество шагов на произвольном вводе.

Здравствуйте, __kot3, Вы писали:

__>Это лишь означает, что в математике даблов нельзя посчитать частичную сумму более чем 10^16 членов этого ряда. Если нужно суммировать меньшее количество, то думаю все получится, если начинать суммировать с конца.
Это означает, что одна и та же формула имеет разную семантику в символьной математике и в математике даблов.
Точно так же, как 5000000000+5000000000 в арифметике даст десять миллиардов, а в арифметике uint даст десять миллиардов по модулю 2^32.
Как трактовать такие формулы — выбор компилятора. Mathematica и Wolfram Alpha трактуют её одним образом; компилятор С++ — другим.

Здравствуйте, Sinclair, Вы писали:

_>>Что такое целое число в терминах МТ?
S>То же самое, что и в обычной алгебре.
Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.

_>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>Всем.
А именно?

_>>Кажется у этой проблемы есть общеизвестное название?
S>Да, halting problem, она же — проблема останова.
_>>Это _алгоритм_ в какой-то теории? Или неизвестно что?
_>>Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?
S>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.

S>Ну так halting problem как раз в том, чтобы понять, глядя на "вычислительный метод" (в терминологии Кнута), является ли он алгоритмом или нет.
S>Тьюринг доказал, что невозможно построить алгоритм, который бы с уверенностью определял, завершится ли произвольная МТ за конечное количество шагов на произвольном вводе.
То есть Тьюринг показал, что доказательство конечности алгоритма должно входить в определение конкретного алгоритма, иначе это не алгоритм.

Здравствуйте, fin_81, Вы писали:
_>Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.
Что такое "строит"?

_>>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>>Всем.
_>А именно?
Определение — это формальная конструкция, описывающая свойства определяемого объекта.
Детектирование — это процесс проверки конкретного объекта на предмет наличия соответствующих свойств.

S>>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
_>Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.
Ну да, неформальное. Собственно МТ, ЧРФ, и лямбда-исчисление и появились в результате попыток формализовать понятие "алгоритм".
У Тьюринга аналогом понятия алгоритм как раз является конкретная МТ. Любая МТ описывает некое вычисление. В том числе и та, которая аналогична 10 GOTO 10.
К сожалению, не все такие вычисления когда-либо заканчиваются.

Здравствуйте, Sinclair, Вы писали:

_>>Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.
S>Что такое "строит"?
Например упорядоченное множество {1,2,3} можно представить как {|,||,|||}. Как построить множество целых чисел?

_>>>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>>>Всем.
_>>А именно?
S>Определение — это формальная конструкция, описывающая свойства определяемого объекта.
S>Детектирование — это процесс проверки конкретного объекта на предмет наличия соответствующих свойств.

S>>>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
_>>Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.
S>Ну да, неформальное. Собственно МТ, ЧРФ, и лямбда-исчисление и появились в результате попыток формализовать понятие "алгоритм".
S>У Тьюринга аналогом понятия алгоритм как раз является конкретная МТ. Любая МТ описывает некое вычисление. В том числе и та, которая аналогична 10 GOTO 10.
S>К сожалению, не все такие вычисления когда-либо заканчиваются.

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

Здравствуйте, fin_81, Вы писали:
_>Например упорядоченное множество {1,2,3} можно представить как {|,||,|||}. Как построить множество целых чисел?
что такое {|, ||, |||}? Последовательность состояний ленты в МТ?

Здравствуйте, fin_81, Вы писали:

_>у нас разное понимание алгоритма.

У вас с Тьюрингом — определенно разное

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>У вас с Тьюрингом — определенно разное

Алгоритм по Тьюрингу должен вычисляться (вычисляться с достижением конечного состояния) на машине Тьюринга. Это аксиома. Вроде.

Здравствуйте, fin_81, Вы писали:

_>Алгоритм по Тьюрингу должен вычисляться (вычисляться с достижением конечного состояния) на машине Тьюринга. Это аксиома. Вроде.

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

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Для того, чтобы алгоритм являлся таковым по Тьюрингу совершенно необязательно, чтобы конечное состояние достигалось за конечное же время. Тьюринг подобного никогда не утверждал, по крайней мере. Любой алгоритм с хотя бы линейной зависимостью времени выполнения от объема входных данных, на практике не достигнет конечного состояния, обрабатывая их бесконечную последовательность. Даже более того, алгоритмы вообще не имеющие явной зависимости по времени выполнения от входных данных, также имеют полное право не завершиться за конечное время. Например, вычисление иррациональных чисел или перечисление целых, как было упомянуто выше. Но при этом, они будут являться алгоритмами по Тьюрингу.

Написанный ответ куда-то пропал. Писать не хочу. В общем сдаюсь. Пусть будет как будет.

Здравствуйте, мыщъх, Вы писали:

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

В ленивом языке бесконечный цикл можно даже и не выполнять, а просто считать выполненным... Серьезно, в Haskell даже есть два обозначения, подходящие под понятие бесконечного цикла. Значение undefined можно использовать в коде, а еще там есть (_|_), и это не шутка

Здравствуйте, мыщъх, Вы писали:

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

Из матанализа мы знаем, что некоторые бесконечные циклы люди выполняют за вполне конечное время. Например:

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

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

Сначала попробую пояснить на примере. Как известно, нет аналитического способа выбрать случайный элемент из бесконечного множества при соблюдении равновероятностного условия. Однако в аналоговом мире это не совсем так. Возьмём, например, жидкостный переменный резистор и установим его в произвольное положение. Ток, который пройдёт через этот резистор, будет некой случайной величиной между возможным максимумом и минимумом и, в идеальном мире, таких произвольных положений было бы бесконечно много... Позволяет ли это задачу? И да, и нет, в зависимости от ответа на вопрос "вам шашечки или ехать?".

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

Следующим шагом в этих рассуждениях следует пристально рассмотреть квантовый компьютер... но в них я не сведущ.

Здравствуйте, мыщъх, Вы писали:

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

class Program
    {
        static void Main(string[] args)
        {
            var index = 1;//думаем, что емкость index может вмещать любое натуральное число
            var sum = 1.;//думаем, что емкость sum может вмещать любую десятичную дробь с бесконечной точностью
            do //думаем, что одна итерация с арифметическими операциями, без Thread.Sleep ничего не занимает по времени
            {
                Thread.Sleep(1/index);//думаем, что данная функция может останавливать выполняющий поток (единственный на машине) на любое число секунд (в виде десятичной дроби) с бесконечной точностью
                index*=2;
                sum += 1.0/index;
            } while (sum!=2.);//с таким условием цикл выполнит бесконечное число итераций

            //Выйдем из бесконечного цикла за 2 секунды
        }
    }

Здравствуйте, kochetkov.vladimir, Вы писали:

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

Но при этом существуют интересные соотношения между требованиями к времени и памяти. Например, недетерминированная МТ, решающая задачу в пределах полиномиальной памяти, может быть сведена к детерминированной, которая так же будет использовать полиномиальную память (хотя когда впервые студенты видят теорему Савича, это кажется удивительным, т.к. казалось бы мы выигрываем экспоненту по времени "за почти просто так").