Здравствуйте, chukichuki, Вы писали:
C>Я думаю одинаковое время выполнения для эквивалентности не столь критично. Его можно опустить.
Можно.
WF>>В таком случае задача "неэквивалентности" — разрешима. Можно написать программу (для МТ), которая получая на вход код двух программ и остановится если они неэквивалентны и зациклится — если эквивалентны.
WF>>Однако обратная задача ("эквивалентности") же — неразрешима, хотя с ходу доказательство я, наверное, и не придумаю. Видимо, надо как-то свести задачу к известной задаче разрешимости (например, к задача об остановке).
C>Я совсем ничего не понял. Разве не (не эквиваленты) != эквиваленты ? В чем разница между задачами "неэквивалентости" и "эквивалентности" ?
Задача эквивалентности выдает 0 (останавливается), если программы П1 и П2 — эквивалентны (в моем определении, но время, в общем-то, можно опустить — оно не существенно). Иначе она зацикливается. Т.е это программа позволяет определить эквивалентность двух программ.
Задача неэквивалентности выдает 0 (останавливается), если программы П1 и П2 — неэквивалентны. Иначе она зацикливается. Т.е это программа позволяет определить неэквивалентность двух программ.
Это мое определение. На самом деле я немного попутал — в разных топиках у меня разные определения, но в том, на который ты отвечал определения именно такие.
Здравствуйте, Privalov, Вы писали:
P>А зачем добавлять в определение время выполнения? Опять же, в случае сортировки можно подобрать данные так, что и быстрый метод, и пузырек управятся с ними за одинаковое время. При этом оба метода завершаются и выдают одинаковый результат. Ясно, что в общем случае это не так, однако алгоритмы, imho, остаются эквивалентными для внешнего наблюдателя. Кому из программистов не доводилось менять тот же пузырек в пробной версии на быструю сортировку в рабочей? Производительность меняется, функциональность — нет. Т. е. внешний наблюдатель увидит уменьшение (или увеличение) времени выполнения программы, однако не заметит никаких различий в результатах.
Мне так захотелось. Можно и опустить — по сути это ничего не меняет. Просто разные определения понятия "эквивалентность".
Здравствуйте, WFrag, Вы писали:
P>>Можно ли считать 2 алгоритма эквивалентными, если, получая на входе одинаковые данные, они возвращают одинаковые результаты?
WF>Почему нет? Однако можно определить "эквивалентность" и так:
WF>Две программы Тьюринга (не "алгоритмы", дабы избежать тонкости связанной с определением понятия "алгоритм") считаются эквивалентными, если для любого входного кортежа обе программы завершаются за одинаковое время (или обе зацикливаются) и выдают одинаковый результат.
А если они по-разному зацикливаются? Одна постоянно что-нибудь пишет, другая не делает ничего.
Здравствуйте, Privalov, Вы писали:
P>Отсутствие результата — тоже результат.
Фишка в том, что ты можешь определить, когда две произвольные программы — неэквивалентны, но не можешь (вернее, можешь, но не всегда ) определить когда они эквивалентны.
Здравствуйте, Кодёнок, Вы писали:
Кё>А если они по-разному зацикливаются? Одна постоянно что-нибудь пишет, другая не делает ничего.
Да, это интересный вопрос. В моем определении разные "зацикленности" не разделяются, хотя в реальной жизни они могут иметь смысл (вспомним хотя бы Unix-овый yes ). Упущение.
Здравствуйте, WFrag, Вы писали:
Кё>>А если они по-разному зацикливаются? Одна постоянно что-нибудь пишет, другая не делает ничего.
WF>Да, это интересный вопрос. В моем определении разные "зацикленности" не разделяются, хотя в реальной жизни они могут иметь смысл (вспомним хотя бы Unix-овый yes ). Упущение.
Хотя я не прав. Для МТ вообще бессмысленно понятие "постоянно что-то писать" (нет понятия ввода/вывода), поэтому для МТ такое разделение бессмысленно.
Но такое понятие можно ввести — например, разделять "выхлопы" программы специальным символом, т.е считаем, что программа не возвращается и не модифицирует старые данные (котррые до последнего выведенного разделителя). В таком случае возникает еще одно определение "эквивалентности".
Здравствуйте, WFrag, Вы писали:
WF>Собственно, ты сам себе и противоречишь. Второе предложение собственно и обосновывает, почему нужно строго определять. У каждого — свое интуитивное понимание, не формализовав его говорить о задаче — бессмысленно. Потому что разные поределения будут давать разные задачи. Например, меня бы устроила эквивалентность данная мной в соседней ветке (по результату + времени), с условием, что МТ заменить на что-нибудь более близкое к реалиям (хоть бы даже и на JVM ).
Для каждой ситуации будет своё "строгое" определение. Зачем оно нужно тогда? Какое бы строгое определение ты ни дал, мы всегда будем решать какой-то частный случай задачи об эквивалентности. И всегда найдется человек, который вспомнит их практики случай, когда твоё определение эквивалентности не подойдет и придется решать уже другую задачу об эквивалентности.
Так что определяться тут надо с тем, что вы хотите Например, выделить типичные задачи и решить каждую:
1. Эквивалентность = две функции возвращают одно и то же значение от одних и тех же входных данных. Побочные эффекты и время не волнуют.
2. То же, что и п. 1, но оговоренные побочные эффекты должны совпадать. Например, можно принимать во внимание только вызовы функций из DLL. Время не волнует.
3. п.1 + разница по времени выполнения не более N%, либо всегда (при каждом выполнении), либо статистически (в среднем на 1000 выполнений на разных данных, случайных или подобранных).
4. п.2 + время из п.3
Первый пункт наверное самый простой.
Естественно, речь не идет о машине Тьюринга. Она бесполезна. Наши программы либо что-то считают (возвращают результат), либо что-то делают (побочные эффекты). Вот для них и следует решать задачу эквивалентности.
Здравствуйте, WFrag, Вы писали:
P>>Отсутствие результата — тоже результат.
WF>Фишка в том, что ты можешь определить, когда две произвольные программы — неэквивалентны, но не можешь (вернее, можешь, но не всегда ) определить когда они эквивалентны.
Некий слепоглухонемой папуас, который даже не может отличить, работает компьютер или нет, какие алгоритмы не выполняй, будет получать одинаковые результаты. Все алгоритмы эквивалентны
Здравствуйте, Кодёнок, Вы писали:
Кё>Для каждой ситуации будет своё "строгое" определение. Зачем оно нужно тогда? Какое бы строгое определение ты ни дал, мы всегда будем решать какой-то частный случай задачи об эквивалентности. И всегда найдется человек, который вспомнит их практики случай, когда твоё определение эквивалентности не подойдет и придется решать уже другую задачу об эквивалентности.
Кё>Так что определяться тут надо с тем, что вы хотите Например, выделить типичные задачи и решить каждую:
О чем и речь. Потому что я могу ввести такое определение эквивалентности:
П1 и П2 эквивалентны, если за число шагов N (как правило, нас интересует конечное время ) для любого входного кортежа из конечного множества входных данных D (как правило, память у нас ограничена ) они обе остановятся и выдадут одинаковый результат. Эта задача — разрешима.
Значит, для любого N и D эта задача разрешима. Можно бежать писать программу для N=100лет и |D|=1Тб
То есть некой "общей задачи эквивалентности", без строго определения просто не существует! Это разнве задачи и разные же решения. В одном случае задача — разрешима, в другом — нет. Хотя вроде бы "задача" одна и та же — "эквивалентность".
Кё>1. Эквивалентность = две функции возвращают одно и то же значение от одних и тех же входных данных. Побочные эффекты и время не волнуют.
Кё>2. То же, что и п. 1, но оговоренные побочные эффекты должны совпадать. Например, можно принимать во внимание только вызовы функций из DLL. Время не волнует.
Кё>3. п.1 + разница по времени выполнения не более N%, либо всегда (при каждом выполнении), либо статистически (в среднем на 1000 выполнений на разных данных, случайных или подобранных).
Кё>4. п.2 + время из п.3
Кё>Первый пункт наверное самый простой.
Кё>Естественно, речь не идет о машине Тьюринга. Она бесполезна. Наши программы либо что-то считают (возвращают результат), либо что-то делают (побочные эффекты). Вот для них и следует решать задачу эквивалентности.
Почему? Проще свести задачу к МТ и строго ее решить. Как это делается для вывода (простейший побочный эффект) — я показал (как это сделать для ввода — пока не придумал ). Просто для МТ проще некоторые построения производить, не нужно отвлекаться на мелкие несущественные детали (типа тех же вызовов DLL).
Это, конечно, если интересует некий строгий теоретический результат, а не практическое решение (например, как база со всеми существующими программами). В начальной постановке вопрос был именно теоретический.
Здравствуйте, Кодёнок, Вы писали:
WF>>Фишка в том, что ты можешь определить, когда две произвольные программы — неэквивалентны, но не можешь (вернее, можешь, но не всегда ) определить когда они эквивалентны.
Кё>Некий слепоглухонемой папуас, который даже не может отличить, работает компьютер или нет, какие алгоритмы не выполняй, будет получать одинаковые результаты. Все алгоритмы эквивалентны
Правильно. Это я на протяжении многих топиков и говорю. В топике, на который ты отвечал, эквивалентность — введенная мной (хотя опять же, ограничение по времени можно убрать).
Именно для такой задачи получается именно такой результат — озвученный выше.
Кё>Некий слепоглухонемой папуас, который даже не может отличить, работает компьютер или нет, какие алгоритмы не выполняй, будет получать одинаковые результаты. Все алгоритмы эквивалентны
Этот самый папуас не знает ничего ни о компьютерах, ни об алгоритмах. Алгоритмы не существуют.
Здравствуйте, WFrag, Вы писали:
WF>Почему? Проще свести задачу к МТ и строго ее решить. Как это делается для вывода (простейший побочный эффект) — я показал (как это сделать для ввода — пока не придумал ). Просто для МТ проще некоторые построения производить, не нужно отвлекаться на мелкие несущественные детали (типа тех же вызовов DLL).
Единственное, что свести настоящий недетерминизм к МТ у нас не получится. Если начинаем говорить о недетерминированном выполнении программы на, скажем, x86 можно тут же опуститься до уровня квантовой механики, бога, инопланетянах и на этом закончить рассуждения о программировании вообще.
С другой стороны, можно ограничиться псевдо-недетерминизмом — просто очень сложной функцией выбора от большого кортежа входных параметров (например, программа была запущена в такой-то момент, в это время состояние памяти такое-то, состояние процессора такое-то, температура такая-то, и.т.д).
Здравствуйте, Cyberax, Вы писали:
>> Получается, что теорема Ферма в арифметике Пеано недоказуема?
C>Да, _исключительно_ в рамках арифметики Пеано она, скорее всего, не C>доказуема — известное доказательство требует привлечения кучи других C>аксиоматик.
Опять двадцать пять. СКОРЕЕ ВСЕГО — это не аргумент. Приведите полное доказательство этого факта.
Quintanar wrote:
> C>Да, _исключительно_ в рамках арифметики Пеано она, скорее всего, не > C>доказуема — известное доказательство требует привлечения кучи других > C>аксиоматик. > Опять двадцать пять. СКОРЕЕ ВСЕГО — это не аргумент. Приведите полное > доказательство этого факта.
Видел на arxive'е статью, где это человек пытается доказать. Сейчас ищу ее.
Здравствуйте, chukichuki, Вы писали:
C>Здравствуйте, Glоbus, Вы писали:
G>>Здравствуйте, chukichuki, Вы писали:
C>>>Представим ситуацию. Существует два алгоритма, описывающих по сути одну и ту же операцию. Например, cортировку некоторого массива. Первый алгоритм выполняет сортировку методом "пузырька", второй — быстрой сортировкой (qsort). Алгоритмы записаны на некотором (любом) императивном языке программирования и оформленны в виде подпрограмм, которым на вход поступает массив из n элементов, а на выходе получается массив из n отсоритированных в соотвествии с заданным критерием элементов. Стоит фантастическая задача: разработать алгоритм (программу) при помощи которой можно было бы показать, что два указанных алгоритма эквиваленты с точки зрения выполняемой операции. Анализ алгоритмов должен производится без их выполнения т.е. в статическом режиме. Как вы думаете, решение такой задачи возможно ?
G>>Правильно ли я понял — машина должна сам разрулить, что делают алгоритмы и сказать, что да, они делают одно и тоже (если это так)?
C>Ну в идеале (недостижимом за конечное время — да !
Думается мне, это нереально, потому что машина не знает — что такое сортировки, да и вообдще что такое алгоритмы. Длятого, чтобы понять, что делает алгоритм, нужно обладать дополнительными знаниями — например значть что такое сортировка.
Здравствуйте, Cyberax, Вы писали:
C>Первое утверждение — теорема Геделя о неполноте, смотрится в учебнике C>мат. логики.
Это я знаю.
C>Да, _исключительно_ в рамках арифметики Пеано она, скорее всего, не C>доказуема — известное доказательство требует привлечения кучи других C>аксиоматик.
Ну и что, что требует? Совершенно необязательно, что они необходимы. Жду доказательства.
WFrag wrote:
> C>Да, _исключительно_ в рамках арифметики Пеано она, скорее всего, не > C>доказуема — известное доказательство требует привлечения кучи других > C>аксиоматик. > Ну и что, что требует? Совершенно необязательно, что они необходимы. > Жду доказательства.
С теоремой Ферма — доказательства недоказуемости пока нет. Можно взять
другое утверждение, уже с доказаной недоказуемостью. Например в теории
графов есть одно такое (вернут мне учебник Непейводы по мат. логике —
скажу).
Здравствуйте, Cyberax, Вы писали:
>> C>С теоремой Ферма — доказательства недоказуемости пока нет. >> Я, вероятно, выпал из контекста, но теорема Ферма доказана.
C>Мы говорим про ее недоказуемость в рамках исключительно аксиоматики C>арифметики Пеано.
Прошу прощения
Видимо, надо как-то свести задачу к известной задаче разрешимости (например, к задача об остановке).
— да ! 
