subj. только не просите отсыпать. ко встрече с серьезными веществами вы еще не готовы.
сегодня, получив долгожданную посылку от джа (которая целый месяц шла из островной англии), я задал гуглу долго мучивший меня сабжевый вопрос и обнаружил, что не одинок в своих терзаниях. свыше двухсот тысяч страниц на одном только английском языке. многие статьи нашпигованы математикой и без плана с ними ни за что не разобраться.
насколько я понял, доказательства для общего случая не существует. более того, для частных случаев существуют обратные решения. некоторые бесконечные циклы возможно выполнить за конечное время при наличии бесконечных ресурсов.
а что вы думаете?
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>а что вы думаете?
А что тут думать? Вот пример:
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 * бесконечность], это будет своеобразный программный дзен: бесконечное количество итераций, время выполнения которых стремится к нулю.
Тем не менее, очень интересно взглянуть на статьи, о которых говорил мыщъх.
