Докажите, что множество $%\{\langle a,b\rangle: \varphi_a()=\varphi_b()\}$% не разрешимо.

$%\langle \cdot,\cdot\rangle$% - это функция спаривания Кантора.

$%\varphi_a$% - это функция, которую определяет программа $%a$%

$%\varphi_a()$% означает результат применения программы $%a$% на пустом аргументе

(Обозначения почти как в восьмом примере тут)

задан 24 Окт '19 5:58

изменен 24 Окт '19 6:01

Это как-то должно легко сводиться к любой алгоритмически неразрешимой проблеме. Например, проблеме остановки машин Тьюринга. Один из номеров даже можно фиксировать, считая, что b выдаёт 0 на пустом наборе. Тогда после остановки машины можно потребовать, чтобы программа выдавала 0.

Такого рода упражнения, на мой взгляд, имеют смысл лишь в определённом контексте. Грубо говоря, если про алгоритмически неразрешимые задачи уже что-то известно, то они решаются по-всякому. Но опираться лучше на то, что было только что изучено.

(25 Окт '19 0:52) falcao

Неразрешимость проблемы остановки известна (правда, для регистровых машин, и программы в задаче предполагаются программами для регистровых машин, но я думаю, решение будет более менее одинаковым для них и для машин Тюринга). Можно поподробнее о том как разрешимость данного множества противоречит неразрешимости проблемы остановки? (Я так понимаю, аргументация с выдаванием 0 должна это объяснять?)

(25 Окт '19 17:47) logic

@logic: к программе, которая остановилась, дописываем команду выдать 0 в качестве значения. Пусть это программа a. Пусть b -- программа, всегда выдающая 0. Тогда можно сравнить ф_a() и ф_b(), пользуясь разрешимостью множества пар (от противного). Они равны <=> наша машина (произвольная) останавливается.

(25 Окт '19 18:58) falcao

@falcao Наверное, Вы опустили очевидные детали, но мне "не хватает" начала рассуждений. Вы предполагаете, что какая-то программа остановилась. И предполагаете, что а остановилась. То есть до начала Вашего рассуждения мы запускаем программы а и b на пустом аргументе и смотрим, какая остановится? Почему вообще какая-то остановится? Потом, почему данную программу можно модифицировать?

Можно ли начать рассуждения с предположения противного? Мне кажется, мне так будет понятнее. Пусть данное множество разрешимо....

(26 Окт '19 4:04) logic

...Т.е. существует программа, которая принимает число п(а,б) и смотрит, равны ли ф_а() и ф_б(). Что происходит дальше?

(26 Окт '19 4:06) logic
1

@logic: пусть существует программа, которая принимает число п(a,b) и смотрит, равны ли ф_а() и ф_b(). Покажем, как с её помощью решить проблему остановки. В качестве b берём программу без входа, которая выдаёт 0. Пусть x -- испытуемая программа без входа, про которую мы не знаем, останавливается она или нет. Мы располагаем её текстом. Дописываем к этому тексту в конце оператор выдать 0 при условии остановки (точное описание, как это сделать, зависит от синтаксиса языка программирования -- например, в Pascal мы команду exit заменили бы на write('0'). Эту новую программу обозначаем a=a(x).

(26 Окт '19 11:57) falcao
1

(продолжение) На пустом входе ф_a() не определено, если x не останавливается, и равно 0, если останавливается. Поэтому факт остановки x равносилен тому, что ф_a()=ф_b(). Последнее мы умеем алгоритмически проверять по предположению. Тем самым, получается алгоритм решения проблемы остановки. Противоречие.

Это типичный пример свЕдения одной проблемы к другой. Он в той или иной редакции многократно применяется в задачах. И среди них есть удачные и интересные. Эта конкретная задача выглядит не слишком эффектно.

(26 Окт '19 12:02) falcao

А можно в качестве а(х) взять программу, которая проверяет для каждого натурального z, верно ли T^0(x,z), и если верно, то выдает 0 (а если нет, то автоматически работает бесконечно)? Я опять использую https://fastpic.ru/view/90/2019/1027/d6db42e281dc4a5a02a33d2e94274468.png.html

Будет ли такаой переход от х к а(х) вычислимым (должна существовать программа, трансформирующая х в а(х))?

(27 Окт '19 23:06) logic

@logic: я не вижу смысла заниматься "подгонкой". Судя по всему, автору курса из каких-то соображений проще апеллировать к уже доказанным ранее утверждениям. Тогда имеет смысл ссылаться на ранее полученные алгоритмически неразрешимые задачи. Я так понимаю, здесь неразрешимость проблемы остановки трактуется через предикат T^0. Но по содержанию и по смыслу это всё равно примерно то же самое, а вникать в разные обозначения, честно говоря, очень скучно.

Переход там, конечно, вычислимый, так как понятно, что если мы имеем текст программы x, то никто не мешает её "прогонять" на заданную длину.

(28 Окт '19 2:14) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×49

задан
24 Окт '19 5:58

показан
238 раз

обновлен
28 Окт '19 2:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru