В общем, пусть даны два алгоритма, гарантированно останавливающихся на любом входе (либо нам заранее известно, на каком входе они останавливаются, и проверка производится только на нём (будем называть это корректным входом)). Существует ли алгоритм, выводящий 1, если на любом корректном входе, результат алгоритма будет одинаков, и 0 в остальных случаях? При этом, чтобы его длина зависела не от размера входа, а от длины описания алгоритма.
(Пусть будет даже более строгий вариант: алгоритмы получают на вход натуральное число; оба всегда останавливаются).
При этом я не говорю о вырожденных случаях (типа, два совершенно разных алгоритма в конце умножают число на ноль и получают на выходе ноль), меня интересует именно _структурное сходство_ действий.
Интересуют любые теоремы и работы на эту тему.
Простой пример: сортировка пузырьком и сортировка слиянием. По факту, оба алгоритма делают одно и тоже, что как бы очевидно при анализе мозгом (на уровне "понимания"). Но как это можно формализовать? (требование ко входу из натурального числа сохраняется; все конечные упорядоченные множества натуральных чисел образуют счётное множество)
Конечно, может показаться, что общее для них -- это вводить упорядоченность на множестве, и это касается только описания входных и выходных данных, но ведь что-то общее должно быть в самой их сути!
Я просто второкурсник, сори.
Или хотя бы частные случаи какие.
Не знаю, никогда не задумывался о чём-то таком и не слышал. Но вообще на алгоритм можно смотреть как на отображение, чёрный ящик, что там внутри нам не важно, и уже две функции сравнивать.
В том-то и дело, что такой подход полностью противоположен тому, что я ищу.
И в чём прикол "сравнивать две функции", представленных "чёрными ящиками"? Проверить совпадение на всех входных данных, то есть то, отчего я сразу открестился? Бред.
Связь между алгоритмами и рекурсивными функциями знает любой матшкольник. Здесь важен _конструктивный_ подход.
>Бред
Ну хз, оба твоих алгоритма делают одно и то же, либо ты вдаёшься в то, как они это делают либо не вдаёшься и смотришь на результат. А если вдаваться в то, как всё происходит, то и сходства никакого нет, с одной стороны переборный пузырёк. с другой разделяй и властвуй слияние, какое между ними сходство вообще, кроме результата.
>_конструктивный_
Ну жди конструктуха тогда.
Ну и да, если на всех возможных входах алгоритмы дают один и тот же результат, то разницы между ними с такой "функциональной" точки зрения нет никакой абсолютно, одно и тоже отображение имеем.
Бля, я же всё конкретно описал. Даже вырожденные случаи. (Допустим, алгоритмы умножения и сложения, определённые для на двойке или нуле (но не одновременно), с точки зрения отображений тождественны, но делают они разное).
В чём смысл твоего подхода, ты можешь объяснить? Или ты в каждой бочке затычка?
Меня "мнения" не интересуют, ты до сих пор по существу ничего не сказал. Меня интересуют теоремы по теме: разрешима ли задача, и так далее.
Или мне в нотации машин Тьюринга надо расписать?
Связь между пузырьком и слиянием очевидна, далеко не только по результату. Тебе же, чтобы понять, что эти алгоритмы об одном и том же, не надо проверять все входы. Да вообще никакого входа проверять не надо.
Забавно, недавно из ИСП и ушёл, правда, из отдела машинного обучения.
Попробуй через индукцию Соломонова
Не, я не настолько нулевой. Я сам с ФУПМа с отлами за соответствующие предметы (я могу и +- строго говорить, просто сейчас в этом нет необходимости), и алгебру ~уровень первого-начала второго курса мехмата/матфака. Нужно конкретно по этой теме.
Получается, все алгоритмы разбиваются на классы эквивалентности. Существует ли язык эффективного описания каждого класса? В смысле, такой, что каждое выражение в нём достаточно ёмко, чтобы отличить один класс от другого, но недостаточно, чтобы назвать его решением исходной задачи (то есть он не "диктует" процессору, не машина тьюринга, короче), а просто описывает, каким решение быть должно?
Такой алгоритм невозможен.
Если бы мы дополнительно потребовали бы, чтобы твой распознающий алгоритм завершал свою работу не только на всюду определенных функциях, то его существование было бы запрещено теоремой Райса: для всякого нетривиального класса вычислимых функций C не существует алгоритма, который выдает 1 на всех кодах программ задающих функции из C и выдает 0 на всех остальных кодах вычислимых функций. Нетривиальность C здесь означает, что есть вычислимая функция из C и вычислимая функция не из C. Если бы был алгоритм проверки двух программ на совпадение задаваемых им функций, то подставив программу для функции f(x)=0 вместо одно из входов мы бы получили алгоритм распознающий класс {f}.
В исходной формулировке буквально к теореме Райса задачу видимо не свести, но тот факт, что такого алгоритма не существует легко доказать по теореме Клини о рекурсии. Если не вдаваться в технические подробности, то по-существу теорема Клини говорит, что можно определять программы, которые могут обращаться к своему собственному коду. Предположим, для противоречия, что был бы алгоритм h(x,y) такой, что при подстановке в него кодов программ вычислимых функций он бы выдавал 1 для программ задающих одинаковые вычислимые функции и 0 для программ задающих различные вычислимые функции. Фиксируем программу zero, задающую тождественно нулевую функцию. Определим вычислимую функцию f(x) с использованием теоремы о рекурсии: если h(zero,f) не завершилась за x шагов, то выдаем f(x)=0, если h(zero,f) завершилась за x шагов и её значение 0, то выдаем f(x)=0 и наконец, если h(zero,f) завершилась за x шагов и её значение не 0, то выдаем f(x)=1. Легко видеть, что f завершается на любом входе. f(x) не могла быть тождественна равна 0, так как тогда h(zero,f)=1 и тем самым для достаточно больших x мы бы имели f(x)=1. Но если бы f(x) не была тождественно равна 0, то из определения f следовало бы, что f(x) тождественно равна 0. Противоречие.
Лол, чувак, я же говорил, что вольная трактовка у задачи может быть. Теоремы Райса и Клини я хорошо знаю.
Ответили же уже, большие дяди пишут докторские диссертации на эту тему. Задача PSPACE и PTIME.
Если ты и так понимал, что в общем случае твоя задача неразрешима, то стоило бы об этом явно и написать в вопросе.
Лол, я вроде конкретно написал, что, во-первых, заранее известно, что обе машины останавливаются на любом входе, во-вторых, интересуют любые частные случаи.