Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Если MT останавливается на бесконечном наборе данных, то мы как-бы в принципе не сможем сгенерировать бесконечное количество наборов данных. Опять же, если бы такой MT существовал, то мы генерируем все норы данных, а потом просто проверяем, есть ли данный набор в нём, тем самым решая задачу остановки.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Уточни условие: что должно происходить, если таких наборов бесконечное количество?
Здравствуйте, nikov, Вы писали: N>Здравствуйте, kochetkov.vladimir, Вы писали:
KV>>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается) N>Уточни условие: что должно происходить, если таких наборов бесконечное количество?
Сгенерировать их все, конечно же Важно, чтобы в генерируемой бесконечной последовательности наборов входных данных не появился такой, который бы привел к зависанию исследуемой МТ.
Здравствуйте, Mystic, Вы писали:
M>Если MT останавливается на бесконечном наборе данных, то мы как-бы в принципе не сможем сгенерировать бесконечное количество наборов данных. Опять же, если бы такой MT существовал, то мы генерируем все норы данных, а потом просто проверяем, есть ли данный набор в нём, тем самым решая задачу остановки.
Здравствуйте, kochetkov.vladimir, Вы писали:
N>>Уточни условие: что должно происходить, если таких наборов бесконечное количество?
KV>Сгенерировать их все, конечно же Важно, чтобы в генерируемой бесконечной последовательности наборов входных данных не появился такой, который бы привел к зависанию исследуемой МТ.
То есть в случае бесконечного количества наборов анализатор никогда не останавливается. Требуется ли, чтобы он обязательно остановился в случае конечного количества наборов, после того, как он напечает их все?
Здравствуйте, nikov, Вы писали:
N>Требуется ли, чтобы он обязательно остановился в случае конечного количества наборов, после того, как он напечает их все?
Разумеется, иначе мы не сможем знать, был ли последний сгенерированный набор последним.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Строим МТ, которая зависает до выдачи первого набора.
И делаем голословное утверждение "а вот если бы она не зависла, то уж точно нагенерировала бы те-и-только-те наборы..."
Поэтому в условие задачи надо добавить, что МТ выдаёт наборы с ненулевой скоростью (конечное количетво наборов за конечное время).
Здравствуйте, kochetkov.vladimir, Вы писали:
N>>Требуется ли, чтобы он обязательно остановился в случае конечного количества наборов, после того, как он напечает их все?
KV>Разумеется, иначе мы не сможем знать, был ли последний сгенерированный набор последним.
То есть это требование эквивалентно тому, чтобы в самом начала анализатор сообщал бы количество наборов, которое он после этого напечатает, так? Тогда требуется ли, чтобы в случае бесконечного количества наборов, анализатор вначале сообщил бы нам, что собирается напечатать бесконечное количество наборов? Ведь иначе в случае бесконечного количества наборов мы никогда не узнаем, что их бесконечное количество.
Здравствуйте, nikov, Вы писали:
n> N>>Требуется ли, чтобы он обязательно остановился в случае конечного количества наборов, после того, как он напечает их все?
n> KV>Разумеется, иначе мы не сможем знать, был ли последний сгенерированный набор последним.
n> То есть это требование эквивалентно тому, чтобы в самом начала анализатор сообщал бы количество наборов, которое он после этого напечатает, так? Тогда требуется ли, чтобы в случае бесконечного количества наборов, анализатор вначале сообщил бы нам, что собирается напечатать бесконечное количество наборов? Ведь иначе в случае бесконечного количества наборов мы никогда не узнаем, что их бесконечное количество.
По-моему не эквивалентно. Это вроде зовётся "перечислимое множество". Т.е. можно создать алгоритм, который выдаёт все элементы множества, возможно бесконечного. Например искомым набором может быть множество нат.чисел: МТ может печатать все нат.числа, или, например, все чётные натуральные числа.
Здравствуйте, kochetkov.vladimir, Вы писали:
k> Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Формально доказать не берусь, но интуитивно считаю что такая проблема тоже не разрешима.
Т.к. такая МТ будет Универсальным Решателем.
Скажем, ей можно будет на вход подсунуть любую проблему, скажем, т.Ферма, и ожидать, что она выдаст пустое множество за конечное время. Что уже из-за теоремы Гёделя о неполноте даёт стойкое ощущение, что это невозможно.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Перебираем все наборы данных. Для каждого набора запускаем новый поток. В этом потоке запускаем исследуемую МТ. Если она останавливается — выводим данный набор.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Теорема. Обратная проблема останова алгоритмически не разрешима.
Доказательтво:
Допустим, что эта проблема разрешима. Пусть X есть некоторый алгоритм, который реализует её решение. Возьмём произвольное диофантово уравнение. Очевидно, по нему легко можно построить МТ, которая получает на вход набор значений его переменных, подставляет их в диофантово уравнение, и, если данный набор удовлетворяет диофантовому уравнению, останавливается, иначе уходит в бесконечный цикл. Передадим описание этой МТ алгоритму X, и будем ждать первого результата или остановки алгоритма X. Если мы получили хотя бы один результат, то из этого следует, что данное диофантово уравнение имеет хотя бы одно решение. Таким образом, алгорим X может быть использован для решения 10-й проблемы Гильберта. А как мы знаем из теоремы Матиясевича (aka MRDP), это невозможно. Следовательно, обратная проблема останова алгоритмически не разрешима. QED
Здравствуйте, vsb, Вы писали:
vsb> KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
vsb> Перебираем все наборы данных. Для каждого набора запускаем новый поток. В этом потоке запускаем исследуемую МТ. Если она останавливается — выводим данный набор.
Этот подход неправильно сработает для программы "while(true){}" — т.к. она зависает для всех наборов данных, то эта МТ должна выдать пустой результат, а она зависнет.
Здравствуйте, ·, Вы писали:
vsb>> KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
vsb>> Перебираем все наборы данных. Для каждого набора запускаем новый поток. В этом потоке запускаем исследуемую МТ. Если она останавливается — выводим данный набор. ·>Этот подход неправильно сработает для программы "while(true){}" — т.к. она зависает для всех наборов данных, то эта МТ должна выдать пустой результат, а она зависнет.
Цель — сгенерировать все наборы данных, на которых заданная МТ останавливается, а не выдать пустой результат за конечное время. Это уже усложнение начальной задачи.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)
Это же вроде известно. Язык, строками которого являются пары (m,n), где m — строковое представление МТ, а n — строковое представление набора данных, m останавливается на n, является рекурсивно-перечислимым (но, разумеется, не рекурсивным). Это язык универсальной МТ. Комплементарный ему язык — не является. Принимая первое утверждение за факт, второе доказывается довольно просто: если комплементарный язык является рекурсивно-перечислимым, то возьмем две МТ: первая будет рекурсивно выписывать все слова первого языка, а вторая — второго. В результате для любого набора данных конкретной МТ можно будет за конечное время проверить, какая МТ его сгенерировала, что являлось бы решением проблемы останова.
Здравствуйте, kl, Вы писали:
kl>Это же вроде известно. Язык, строками которого являются пары (m,n), где m — строковое представление МТ, а n — строковое представление набора данных, m останавливается на n, является рекурсивно-перечислимым (но, разумеется, не рекурсивным). Это язык универсальной МТ. Комплементарный ему язык — не является. Принимая первое утверждение за факт, второе доказывается довольно просто: если комплементарный язык является рекурсивно-перечислимым, то возьмем две МТ: первая будет рекурсивно выписывать все слова первого языка, а вторая — второго. В результате для любого набора данных конкретной МТ можно будет за конечное время проверить, какая МТ его сгенерировала, что являлось бы решением проблемы останова.
Вопрос был не в том, является ли язык МТ рекурсивно-перечислимым (он им по определению является, да). Вопрос был в том, возможно ли построить такую МТ, которая генерировала все допустимые строки языка исследуемой МТ, анализируя ее представление?
Здравствуйте, nikov, Вы писали:
N>Теорема. Обратная проблема останова алгоритмически не разрешима.
N>Доказательтво: N>Допустим, что эта проблема разрешима. Пусть X есть некоторый алгоритм, который реализует её решение. Возьмём произвольное диофантово уравнение. Очевидно, по нему легко можно построить МТ, которая получает на вход набор значений его переменных, подставляет их в диофантово уравнение, и, если данный набор удовлетворяет диофантовому уравнению, останавливается, иначе уходит в бесконечный цикл. Передадим описание этой МТ алгоритму X, и будем ждать первого результата или остановки алгоритма X. Если мы получили хотя бы один результат, то из этого следует, что данное диофантово уравнение имеет хотя бы одно решение. Таким образом, алгорим X может быть использован для решения 10-й проблемы Гильберта. А как мы знаем из теоремы Матиясевича (aka MRDP), это невозможно. Следовательно, обратная проблема останова алгоритмически не разрешима. QED
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Вопрос был не в том, является ли язык МТ рекурсивно-перечислимым (он им по определению является, да). Вопрос был в том, возможно ли построить такую МТ, которая генерировала все допустимые строки языка исследуемой МТ, анализируя ее представление?
Не просто "язык МТ" является RE, а язык, кодирующий наборы данных *всех* МТ. На первый взгляд твой вопрос звучит как: можно ли построить универсальную МТ, т.е. машину, которая принимает на вход строку-представление некой МТ, и распознает ее язык. Это и называется "универсальная машина Тьюринга".
Но все ломает требование остановиться в случае конечного числа наборов (в частном случае, пустого). Поскольку вопрос стоит как "разрешима ли задача", надо ее сформулировать в виде decision problem. После этого скорее всего станет очевидно, что неразрешима, т.к. иначе, как показал nikov, ее можно было бы применить для решения неразрешимых задач, где речь идет о существовании единственного набора.
Важно, чтобы в генерируемой бесконечной последовательности наборов входных данных не появился такой, который бы привел к зависанию исследуемой МТ.
Перекуём баги на фичи!
