Простите, наверное, я начинаю уже Вас раздражать, но...
Итак, прежде, чем начать: я ни в коей мере не сомневаюсь в Ваших профессиональных способностях и не стремлюсь Вас задеть или оскорбить (я сам такой — каааак заболею идеей, так всё (последней болезнью у меня был архиватор, сжимающий любую последовательность в функцию ) ). О причинах, по которых я это всё пишу — см. ниже.
GC>Вы сами понимаете что ввод пользователя привносит новую информацию в программу. Пользователь находится вне вычислительной системы, и предугадать его поведение не возможно.
Конечно я понимаю! Я к этому и веду // Хотя в случае с числом "пи" результат от пользователя (который никогда не ошибается и не пытается вводить неправильные числа) как раз детерминирован.
GC>Идет речь о "закрытых" участках кода, в которые информация из внешнего мира не поступает, GC>а только обрабатываются.
Это и есть частные случаи, о который я говорил с самого начала.
Из Ваших ответов:
LF>Вы хотите сказать, что разрешили неразрешимую проблему?
Получается что так.
Получено решение не для общего случая, а для частного — когда система "замкнута". Неразрешимая проблема осталась таковой.
F>Что вы хотите услышать? Что разработчик, скачав утилиту и натравив ее на исходный код, получит (если получит) неоднозначные результаты и за это еще денег надо будет отвалить?
Вся фишка в том, что результаты будут 100% однозначные и 100% достоверные.
// Флейм пошёл из-за уверености в выделенном.
Полный перебор всех вариантов даст 100% однозначные и достоверные результаты, но "кому это надо" (c)? Если метод через 100 лет выдаст результат, что программа не зациклится, что с ним будут делать пра-правнуки того программиста, что запустил задачу на выполнение? А если алгоритм зацикливается и результаты его предсказать нельзя (скажем, алгоритм пользуется неким ГПСЧ, обладающий очень долго вычисляющимся алгоритмом (неупрощаемым) и проще запустить этот ГПСЧ и получить результат, чем пытаться предсказать (траты времени будут соответствующие))? Остановится через бесконечное время?
в разделе "Common pitfalls" (Распространенные заблуждения)
указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний.
Машина Тьюринга является машиной с бесконечным числом состояний.
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Лично я пытаюсь отговорить Вас от попытки распространить решение на все случаи и создавать некий инструмент, который будет 100% выдавать правильный результат. Число случаев использования такого инструмента будет сильно ограничено (мало разрабатываемых систем являются "закрытыми" без поступления внешних данных, а те элементарные функции, на которые можно будет анализатор натравить... Стоит ли овчинка выделки?).
Однако, раз Вы уж занялись этой проблемой, то у Вас может получится отличный полуавтоматический генератор юнит-тестов, который не будет выдавать информацию зациклилось/не зациклилось, а просто прогонит функцию по наибольшему количеству нужных данных :
int func ( int const arg ) {
if ( arg < 2 ) {
return -1;
}
else if ( arg * 2 > 15 ) {
return 8;
}
else {
return 5;
}
}
Аааа, после того топика мне в голову пришла мысль о анализаторе, примерно о таком же, о котором пишет GhostCoders Перебор осмысленных вариантов на основе условий выполнения и условий циклов внутри тестируемой функции Только мысль была отметена за минуту
Re[3]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>Вот пример данной функции на этом языке: GC>* This is function from RomikT *
Спасибо, что не поленился перевести!
А можно теперь условие n!=1 заменить на n>1 (RomikT там накосячил), и тип данных заменить на целые числа (или хотя бы 64-битные)?
Здравствуйте, GhostCoders, Вы писали:
C>>Вот только это число растёт просто НЕВООБРАЗИМО быстро. Для машины Тьюринга с лентой из 6 элементов _нижняя_ граница составляет 10^1439 шагов (другой автор цитирует 4096 ^^ 166). GC>Это зависит от числа возможных состояний головки машины Тьюринга. Чем оно больше тем больше шагов.
Для любого реального компьютера это число будет таким, что я даже не знаю как его записать.
C>>Причём не существует общих способов анализа проблемы останова для алгоритма, работающих за меньшее число шагов, чем сам алгоритм. Т.е. тебе для анализа вполне вероятно может потребоваться выполнить эти 10^1439 шагов. GC>А за большее число шагов или за равное — существуют такие алгоритмы.
Тогда проще запустить сам алгоритм.
C>>Так что любой общий алгоритм анализа — это изобретение вечного двигателя. GC>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?
Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx
Скажем если число N — четно, то оно уменьшается в два раза. То есть стремиться к единице. Тут все оцевидно.
Если число нечетно, то нечетно число O можно представить через четное число E следующим образом:
O = 2 * E + 1.
(Скажем 17 можно представить как 2 * 8 + 1), где O = 17, E = 8.
Для нечетных чисел производиться операция N = 3 * N + 1, то есть имеем следующее
O* = 3 * (2 * E + 1) + 1 = 6 * E + 3 + 1 = 6 * E + 4;
то есть на следующей итерации имеем число O* = 6 * E + 4;
Но оно всегда будет четным, так как если четно Е, то умножение четного числа на любое другое число
дает четное число, придавление 4 картины не изменеят, так как 4 — четное.
Следовательно, следующий шаг деление на 2.
Имеем O** = 3 * E + 2.
Число O** — тоже четное по тем же причинам.
Следовательно, следующий шаг деление на 2.
Имеем O*** = 3 * E / 2 + 1.
Несмотря на то что Е — четное, мы не может гарантировать что E / 2 — тоже четное.
Тут возможны обе ситуации.
Но имеет следующее.
Изначально мы имели нечетное число O, которое было равно O = 2 * E + 1.
после одного шага HOTPO, и двух шагов деления на 2, имеем O*** = 3 * E / 2 + 1.
Очевидно, что O*** < O.
(O*** всегда меньше O, для значений E > 1).
Получается что в любом случае, значение исходного числа N уменьшается, то есть стремиться к 1.
Через конечное число шагов мы получаем значение 1.
Где мои 1000 фунтов стерлингов???
Третий Рим должен пасть!
Re[6]: Реализован простейший язык для тестирования на зацик
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, GhostCoders, Вы писали:
C>>>Вот только это число растёт просто НЕВООБРАЗИМО быстро. Для машины Тьюринга с лентой из 6 элементов _нижняя_ граница составляет 10^1439 шагов (другой автор цитирует 4096 ^^ 166). GC>>Это зависит от числа возможных состояний головки машины Тьюринга. Чем оно больше тем больше шагов. C>Для любого реального компьютера это число будет таким, что я даже не знаю как его записать.
C>>>Причём не существует общих способов анализа проблемы останова для алгоритма, работающих за меньшее число шагов, чем сам алгоритм. Т.е. тебе для анализа вполне вероятно может потребоваться выполнить эти 10^1439 шагов. GC>>А за большее число шагов или за равное — существуют такие алгоритмы. C>Тогда проще запустить сам алгоритм.
C>>>Так что любой общий алгоритм анализа — это изобретение вечного двигателя. GC>>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно? C>Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx
Здравствуйте, GhostCoders, Вы писали:
GC>Здравствуйте, D. Mon, Вы писали:
DM>>Здравствуйте, GhostCoders, Вы писали:
DM>>Фишка исходной задачи тут: DM>>http://en.wikipedia.org/wiki/Collatz_conjecture DM>>http://mathworld.wolfram.com/CollatzProblem.html DM>>если решишь для случая целых чисел (в математическом смысле), 1000 фунтов стерлингов получишь сразу, другие премии позже.
GC>Доказывается элементарно.
GC>Скажем если число N — четно, то оно уменьшается в два раза. То есть стремиться к единице. Тут все оцевидно.
GC>Если число нечетно, то нечетно число O можно представить через четное число E следующим образом:
GC> O = 2 * E + 1.
Возьмём число 7 = 2 * 3 + 1
GC>(Скажем 17 можно представить как 2 * 8 + 1), где O = 17, E = 8.
GC>Для нечетных чисел производиться операция N = 3 * N + 1, то есть имеем следующее
GC> O* = 3 * (2 * E + 1) + 1 = 6 * E + 3 + 1 = 6 * E + 4;
GC>то есть на следующей итерации имеем число O* = 6 * E + 4; GC>Но оно всегда будет четным, так как если четно Е, то умножение четного числа на любое другое число GC>дает четное число, придавление 4 картины не изменеят, так как 4 — четное.
GC>Следовательно, следующий шаг деление на 2.
GC>Имеем O** = 3 * E + 2.
O** = 3 * 3 + 2 = 11
GC>Число O** — тоже четное по тем же причинам.
11 — чётное?
(ну и хотелось бы услышать, что за "те же причины")
Здравствуйте, Alexey F, Вы писали:
AF>Аааа, после того топика мне в голову пришла мысль о анализаторе, примерно о таком же, о котором пишет GhostCoders Перебор осмысленных вариантов на основе условий выполнения и условий циклов внутри тестируемой функции Только мысль была отметена за минуту
Рекомендую посмотреть, как работает Pex (сделанный в Microsoft Research). Была презентация на PDC.
Re[7]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>>>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно? C>>Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx
GC>Решение есть, только будет очень долгим. АНАЛИЗАТОР существует.
Ну так какое решение-то? Перебрать все варианты циклов? Тогда это совершенно несерьёзно.
Нормальные статические валидаторы кода работают за счёт того, что строят логическую модель программы и пытаются в ней доказывать теоремы (о том, что имеем выход индекса за границу, обращение по невалидному указателю и т.п.). Если такая теорема доказывается — это означает ошибку.
Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны.
Sapienti sat!
Re[5]: Реализован простейший язык для тестирования на зацик
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, GhostCoders, Вы писали:
GC>>>>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно? C>>>Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx
GC>>Решение есть, только будет очень долгим. АНАЛИЗАТОР существует. C>Ну так какое решение-то? Перебрать все варианты циклов? Тогда это совершенно несерьёзно.
C>Нормальные статические валидаторы кода работают за счёт того, что строят логическую модель программы и пытаются в ней доказывать теоремы (о том, что имеем выход индекса за границу, обращение по невалидному указателю и т.п.). Если такая теорема доказывается — это означает ошибку.
C>См. сюда: http://en.wikipedia.org/wiki/Satisfiability_Modulo_Theories и http://verify.stanford.edu/SVC/
C>Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны.
Ещё по идее есть "обратный" подход — Total functional programming, в нём целеноправленно сделаны ограничения, чтобы получать явно завершающуюся программу. Правда, пока это до реальных реализации не дошло вроде как.
Re[9]: Реализован простейший язык для тестирования на зацик
Здравствуйте, Курилка, Вы писали:
C>>Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны. К>Ещё по идее есть "обратный" подход — Total functional programming, в нём целеноправленно сделаны ограничения, чтобы получать явно завершающуюся программу. Правда, пока это до реальных реализации не дошло вроде как.
Уже дошло, даже на практике начинает использоваться — http://augeas.net/
Нужно найти 123124.
На вход поступает 123123124.
Если мы очистим буфер (начнём поиск совпадения сначала) при поступлении второй 3, то пропустим совпадение.
Тут нужен сдвиг.
Это нечто вроде (а может и он самый) алгоритма Боуера-Мура поиска подстроки.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Курилка, Вы писали:
C>>>Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны. К>>Ещё по идее есть "обратный" подход — Total functional programming, в нём целеноправленно сделаны ограничения, чтобы получать явно завершающуюся программу. Правда, пока это до реальных реализации не дошло вроде как. C>Уже дошло, даже на практике начинает использоваться — http://augeas.net/
Чтот не вижу при чём тут TFP
Бумеранговские линзы гарантированно тотальны?
Ну и речь всёж идёт от языке общего применения.
Здравствуйте, SergeCpp, Вы писали:
SC>Нужно найти 123124. SC>На вход поступает 123123124. SC>Если мы очистим буфер (начнём поиск совпадения сначала) при поступлении второй 3, то пропустим совпадение. SC>Тут нужен сдвиг. SC>Это нечто вроде (а может и он самый) алгоритма Боуера-Мура поиска подстроки.
Да, я поторопился
Спасибо за уточнение
Re[11]: Реализован простейший язык для тестирования на заци
Здравствуйте, Курилка, Вы писали:
C>>Уже дошло, даже на практике начинает использоваться — http://augeas.net/ К>Чтот не вижу при чём тут TFP К>Бумеранговские линзы гарантированно тотальны?
Нет, но они используют результаты исследований в области TFP.
К>Ну и речь всёж идёт от языке общего применения.
Это вряд ли.
Sapienti sat!
Re: Реализован простейший язык для тестирования на зациклив
Здравствуйте, GhostCoders, Вы писали:
GC>Реализовал транслятор простейшего языка программирования. GC>Для целей тестирования алгоритма, который определеят зависает ли определенная программа, GC>и если зависает то на каких наборах данных.
Проверьте вашей программой вашу же программу
Re[11]: Реализован простейший язык для тестирования на заци
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, Курилка, Вы писали:
К>>Ну и речь всёж идёт от языке общего применения.
FR>Он же будет не Тьюринг полный.
В том и смысл, что мощность машины Тьюринга избыточна, по меньшей мере для большинства задач.
Как пример — реальные машины не обладают бесконечной памятью (в отличие от классической МТ с бесконечной лентой)
Re[13]: Реализован простейший язык для тестирования на заци
Здравствуйте, Курилка, Вы писали:
К>В том и смысл, что мощность машины Тьюринга избыточна, по меньшей мере для большинства задач.
Есть куча задач где она недостаточна, ждем квантовые вычислители.
Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
К>Как пример — реальные машины не обладают бесконечной памятью (в отличие от классической МТ с бесконечной лентой)
(последней болезнью у меня был архиватор, сжимающий любую последовательность в функцию 
) ). О причинах, по которых я это всё пишу — см. ниже.
А если алгоритм зацикливается и результаты его предсказать нельзя (скажем, алгоритм пользуется неким ГПСЧ, обладающий очень долго вычисляющимся алгоритмом (неупрощаемым) и проще запустить этот ГПСЧ и получить результат, чем пытаться предсказать (траты времени будут соответствующие))? Остановится через бесконечное время?
:
