8 Кб, 1680x1050Всем салют.
В общем, пусть даны два алгоритма, гарантированно останавливающихся на любом входе (либо нам заранее известно, на каком входе они останавливаются, и проверка производится только на нём (будем называть это корректным входом)). Существует ли алгоритм, выводящий 1, если на любом корректном входе, результат алгоритма будет одинаков, и 0 в остальных случаях? При этом, чтобы его длина зависела не от размера входа, а от длины описания алгоритма.
(Пусть будет даже более строгий вариант: алгоритмы получают на вход натуральное число; оба всегда останавливаются).
При этом я не говорю о вырожденных случаях (типа, два совершенно разных алгоритма в конце умножают число на ноль и получают на выходе ноль), меня интересует именно _структурное сходство_ действий.
Интересуют любые теоремы и работы на эту тему.
Простой пример: сортировка пузырьком и сортировка слиянием. По факту, оба алгоритма делают одно и тоже, что как бы очевидно при анализе мозгом (на уровне "понимания"). Но как это можно формализовать? (требование ко входу из натурального числа сохраняется; все конечные упорядоченные множества натуральных чисел образуют счётное множество)
Конечно, может показаться, что общее для них -- это вводить упорядоченность на множестве, и это касается только описания входных и выходных данных, но ведь что-то общее должно быть в самой их сути!
Я просто второкурсник, сори.
В общем, пусть даны два алгоритма, гарантированно останавливающихся на любом входе (либо нам заранее известно, на каком входе они останавливаются, и проверка производится только на нём (будем называть это корректным входом)). Существует ли алгоритм, выводящий 1, если на любом корректном входе, результат алгоритма будет одинаков, и 0 в остальных случаях? При этом, чтобы его длина зависела не от размера входа, а от длины описания алгоритма.
(Пусть будет даже более строгий вариант: алгоритмы получают на вход натуральное число; оба всегда останавливаются).
При этом я не говорю о вырожденных случаях (типа, два совершенно разных алгоритма в конце умножают число на ноль и получают на выходе ноль), меня интересует именно _структурное сходство_ действий.
Интересуют любые теоремы и работы на эту тему.
Простой пример: сортировка пузырьком и сортировка слиянием. По факту, оба алгоритма делают одно и тоже, что как бы очевидно при анализе мозгом (на уровне "понимания"). Но как это можно формализовать? (требование ко входу из натурального числа сохраняется; все конечные упорядоченные множества натуральных чисел образуют счётное множество)
Конечно, может показаться, что общее для них -- это вводить упорядоченность на множестве, и это касается только описания входных и выходных данных, но ведь что-то общее должно быть в самой их сути!
Я просто второкурсник, сори.
Или какая-то метрика существует для оценки схожести действий алгоритма... То есть, чтобы оценить тождественность двух алгоритмов, нужно было не доказывать для обоих случаев, что появляется одна и та же структура на выходе (ну, вроде, доказывать для каждого алгоритма перемножения матриц то, что это именно перемножение матриц), а находить инвариант в самих действиях.
Или хотя бы частные случаи какие.
Или хотя бы частные случаи какие.
>>1688 (OP)
Не знаю, никогда не задумывался о чём-то таком и не слышал. Но вообще на алгоритм можно смотреть как на отображение, чёрный ящик, что там внутри нам не важно, и уже две функции сравнивать.
Не знаю, никогда не задумывался о чём-то таком и не слышал. Но вообще на алгоритм можно смотреть как на отображение, чёрный ящик, что там внутри нам не важно, и уже две функции сравнивать.
>>1691
В том-то и дело, что такой подход полностью противоположен тому, что я ищу.
И в чём прикол "сравнивать две функции", представленных "чёрными ящиками"? Проверить совпадение на всех входных данных, то есть то, отчего я сразу открестился? Бред.
Связь между алгоритмами и рекурсивными функциями знает любой матшкольник. Здесь важен _конструктивный_ подход.
В том-то и дело, что такой подход полностью противоположен тому, что я ищу.
И в чём прикол "сравнивать две функции", представленных "чёрными ящиками"? Проверить совпадение на всех входных данных, то есть то, отчего я сразу открестился? Бред.
Связь между алгоритмами и рекурсивными функциями знает любой матшкольник. Здесь важен _конструктивный_ подход.
>>1692
Ну хз, оба твоих алгоритма делают одно и то же, либо ты вдаёшься в то, как они это делают либо не вдаёшься и смотришь на результат. А если вдаваться в то, как всё происходит, то и сходства никакого нет, с одной стороны переборный пузырёк. с другой разделяй и властвуй слияние, какое между ними сходство вообще, кроме результата.
Ну жди конструктуха тогда.
>Бред
Ну хз, оба твоих алгоритма делают одно и то же, либо ты вдаёшься в то, как они это делают либо не вдаёшься и смотришь на результат. А если вдаваться в то, как всё происходит, то и сходства никакого нет, с одной стороны переборный пузырёк. с другой разделяй и властвуй слияние, какое между ними сходство вообще, кроме результата.
>_конструктивный_
Ну жди конструктуха тогда.
>>1692
Ну и да, если на всех возможных входах алгоритмы дают один и тот же результат, то разницы между ними с такой "функциональной" точки зрения нет никакой абсолютно, одно и тоже отображение имеем.
Ну и да, если на всех возможных входах алгоритмы дают один и тот же результат, то разницы между ними с такой "функциональной" точки зрения нет никакой абсолютно, одно и тоже отображение имеем.
>>1697
Бля, я же всё конкретно описал. Даже вырожденные случаи. (Допустим, алгоритмы умножения и сложения, определённые для на двойке или нуле (но не одновременно), с точки зрения отображений тождественны, но делают они разное).
В чём смысл твоего подхода, ты можешь объяснить? Или ты в каждой бочке затычка?
Меня "мнения" не интересуют, ты до сих пор по существу ничего не сказал. Меня интересуют теоремы по теме: разрешима ли задача, и так далее.
Или мне в нотации машин Тьюринга надо расписать?
Связь между пузырьком и слиянием очевидна, далеко не только по результату. Тебе же, чтобы понять, что эти алгоритмы об одном и том же, не надо проверять все входы. Да вообще никакого входа проверять не надо.
Бля, я же всё конкретно описал. Даже вырожденные случаи. (Допустим, алгоритмы умножения и сложения, определённые для на двойке или нуле (но не одновременно), с точки зрения отображений тождественны, но делают они разное).
В чём смысл твоего подхода, ты можешь объяснить? Или ты в каждой бочке затычка?
Меня "мнения" не интересуют, ты до сих пор по существу ничего не сказал. Меня интересуют теоремы по теме: разрешима ли задача, и так далее.
Или мне в нотации машин Тьюринга надо расписать?
Связь между пузырьком и слиянием очевидна, далеко не только по результату. Тебе же, чтобы понять, что эти алгоритмы об одном и том же, не надо проверять все входы. Да вообще никакого входа проверять не надо.
Вдобавок, какой смысл сравнивать входы? У всех нетривиальных алгоритмов счётная область определения, то есть на любых двух нетривиальных алгоритмах время работы бесконечное.
Нашёл. http://www.ispras.ru/proceedings/docs/2015/27/4/isp_27_2015_4_145.pdf
Забавно, недавно из ИСП и ушёл, правда, из отдела машинного обучения.
Забавно, недавно из ИСП и ушёл, правда, из отдела машинного обучения.
И вообще всё подобное +- легко гуглится по "эквивалентность программ". Но всё же вопрос, какой труд фундаментальный по этой теме, остаётся открытым. И теоретические ограничения.
Этой темой занимается Захаров, автореферат его докторской диссертации тут скачать можно: http://vak1.ed.gov.ru/ru/dissertation/subscription/index.php?id54=14398&from54=102
>>1688 (OP)
Попробуй через индукцию Соломонова
Попробуй через индукцию Соломонова
>>1718
Не, я не настолько нулевой. Я сам с ФУПМа с отлами за соответствующие предметы (я могу и +- строго говорить, просто сейчас в этом нет необходимости), и алгебру ~уровень первого-начала второго курса мехмата/матфака. Нужно конкретно по этой теме.
Не, я не настолько нулевой. Я сам с ФУПМа с отлами за соответствующие предметы (я могу и +- строго говорить, просто сейчас в этом нет необходимости), и алгебру ~уровень первого-начала второго курса мехмата/матфака. Нужно конкретно по этой теме.
Теперь добавлю ещё один вопрос:
Получается, все алгоритмы разбиваются на классы эквивалентности. Существует ли язык эффективного описания каждого класса? В смысле, такой, что каждое выражение в нём достаточно ёмко, чтобы отличить один класс от другого, но недостаточно, чтобы назвать его решением исходной задачи (то есть он не "диктует" процессору, не машина тьюринга, короче), а просто описывает, каким решение быть должно?
Получается, все алгоритмы разбиваются на классы эквивалентности. Существует ли язык эффективного описания каждого класса? В смысле, такой, что каждое выражение в нём достаточно ёмко, чтобы отличить один класс от другого, но недостаточно, чтобы назвать его решением исходной задачи (то есть он не "диктует" процессору, не машина тьюринга, короче), а просто описывает, каким решение быть должно?
>>1688 (OP)
Такой алгоритм невозможен.
Если бы мы дополнительно потребовали бы, чтобы твой распознающий алгоритм завершал свою работу не только на всюду определенных функциях, то его существование было бы запрещено теоремой Райса: для всякого нетривиального класса вычислимых функций 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. Противоречие.
Такой алгоритм невозможен.
Если бы мы дополнительно потребовали бы, чтобы твой распознающий алгоритм завершал свою работу не только на всюду определенных функциях, то его существование было бы запрещено теоремой Райса: для всякого нетривиального класса вычислимых функций 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. Противоречие.
>>2354
Лол, чувак, я же говорил, что вольная трактовка у задачи может быть. Теоремы Райса и Клини я хорошо знаю.
Ответили же уже, большие дяди пишут докторские диссертации на эту тему. Задача PSPACE и PTIME.
Лол, чувак, я же говорил, что вольная трактовка у задачи может быть. Теоремы Райса и Клини я хорошо знаю.
Ответили же уже, большие дяди пишут докторские диссертации на эту тему. Задача PSPACE и PTIME.
>>2366
Если ты и так понимал, что в общем случае твоя задача неразрешима, то стоило бы об этом явно и написать в вопросе.
Если ты и так понимал, что в общем случае твоя задача неразрешима, то стоило бы об этом явно и написать в вопросе.
>>2367
Лол, я вроде конкретно написал, что, во-первых, заранее известно, что обе машины останавливаются на любом входе, во-вторых, интересуют любые частные случаи.
Лол, я вроде конкретно написал, что, во-первых, заранее известно, что обе машины останавливаются на любом входе, во-вторых, интересуют любые частные случаи.
>>2369
Если что, я в последнем абзаце своего поста как раз и написал как доказывать неразрешимость именно в предположение, что на вход подаются программы всегда завершающие свою работу.
Если что, я в последнем абзаце своего поста как раз и написал как доказывать неразрешимость именно в предположение, что на вход подаются программы всегда завершающие свою работу.