Докажите, что множество $%\{p:\phi_p(x) \text{ останавливается для всех } x\}$% не является рекурсивно перечислимым, т.е. что не существует программы $%q$%, для которой $$\{p:\phi_p(x) \text{ останавливается для всех } x\}=\{x:\phi_q(x)\text{ останавливается}\}$$

задан 26 Окт '19 22:38

10|600 символов нужно символов осталось
1

Задач похожего типа на форуме было много. Там лишь слегка отличается терминология.

Идея здесь стандартная: рассуждаем от противного, показывая, как алгоритмически решить проблему остановки на основе процедуры перечисления всюду определённых программ с входом x.

Рассмотрим произвольную машину M без входа. Составим программу p(M), которая явно строится по описанию машины M. Программа p(M) работает на входе x, прогоняя M на x шагов. Если M за это время не остановилась, программа что-то выдаёт в качестве результата. Что конкретно -- не важно: мы можем считать, что это всегда 0, или же что это x. Если же за время <=x машина M остановилась, мы загоняем нашу программу в бесконечный цикл.

Построенная программа обладает свойством: M не останавливается за конечное время <=> p(M) всюду определена. Теперь проблема остановки решается так: мы запускаем машину M и ждём её остановки. Если она останавливается за конечное время, мы этой остановки дождёмся и дадим ответ "да". Параллельно мы запускаем перечисляющую процедуру для всюду определённых программ, существование которой мы предположили. Если M за конечное время не останавливается, то мы дождёмся появления программы p(M) на печати у этой процедуры.

ссылка

отвечен 26 Окт '19 23:27

изменен 27 Окт '19 14:17

Начиная с "Теперь проблема остановки решается так" становится непонятно. Сначала, как я понимаю, мы рассматриваем программу, которая принимает программу Й и выдает 1 если ф_Й() останавливается, а иначе уходит в бесконечный цикл. Применяем эту программу к Й=M.

Потом идет "Параллельно мы запускаем перечисляющую процедуру для всюду определённых программ, существование которой мы предположили". Что называется перечисляющей процедурой? Наше предположение заключается в том, что два множества из вопроса равны. Откуда предположение о том, что существуют всюду определенные программы?

(27 Окт '19 0:30) logic

@logic: давайте "раскручивать" вопрос с осознания каких-то совсем простых вещей. Откуда предположение о том, что существуют всюду определенные программы? Это не предположение, а нечто очевидное. Представьте себе программу, которая прибавляет в числу единицу. Вы ему на вход даёте x, а она на выход x+1. Или Вы даёте x, а она выдаёт x^2. Или даёте x, а она выдаёт 0 независимо от x. А бывают программы, которые на каких-то входах останавливается, а на каких-то работают бесконечно долго.

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

(27 Окт '19 0:47) falcao

(продолжение) Множество называется перечислимым, если его элементы можно напечатать. То есть существует бесконечно долго работающая программа (алгоритмическая процедура), которая в каком-то порядке время от времени печатает элементы данного множества, и никакие другие не печатает. Это и есть перечисляющая процедура. От этого интуитивно понятного определения надо дальше переходить к его формальным версиям. Одна из которых такова: перечислимое множество является либо пустым, либо множеством значений некоторой всюду определённой вычислимой функции.

(27 Окт '19 0:49) falcao

Хорошо, давайте пока использовать определение через перечисление. В любом случае, мы хотим показать, что существует программа W которая принимает программу Й и выдает 1 если ф_Й() останавливается и 0 если ф_Й() не останавливается. Как существование такой программы следует из того, что "Если M за конечное время не останавливается, то мы дождёмся появления программы p(M) на печати у этой процедуры"?

(27 Окт '19 1:16) logic

@logic: я доказываю, что множество всюду определённых программ (то, которое определено в самом начале текста вопроса) не является рекурсивно перечислимым. Это я делаю от противного, и в деталях описываю, как гипотеза о его перечислимости влечёт противоречие (в виде получения алгоритма, решающего проблему остановки). По этому рассуждению, и в моих обозначениях, у Вас есть какие-либо вопросы? Если да, то задайте их. А если нет, то далее можно перейти к объяснению того, почему доказано то, что написано в последней строчке вопроса (то есть, почему там говорится о том же самом).

(27 Окт '19 2:10) falcao

@falcao: по Вашему рассуждению есть вопрос, который я попытался написать в предыдущем комментарии. А именно, как из последнего предложения Вашего ответа (которое понятно) получается существование алгоритма, решающего проблему остановки?

(27 Окт '19 2:22) logic

@logic: там идея та же, что при доказательстве важной теоремы о том, что множество A разрешимо <=> A перечислимо вместе со своим дополнением A'. Напомню, что там есть два устройства -- одно печатает элементы A, другое -- элементы A'. Мы сидим и ждём. Когда одна из машин напечатает число, мы узнаем, принадлежит оно A или A'.

Здесь также есть два "параллельных" процесса. Один -- работа самой машины M. Если она останавливается, то первый процесс об этом "скажет". А если нет, то программа p(M) окажется всюду определённой по построению, и тогда её номер будет напечатан перечисляющей программой.

(27 Окт '19 3:36) falcao

@falcao: Теперь вроде понятно (по модулю эквивалентности определений рекурсивной перечислимости). Теперь действительно можно "перейти к объяснению того, почему доказано то, что написано в последней строчке вопроса". (Если я правильно понимаю, в этой цитате Вы как раз имеете в виду эквивалентность определений).

(27 Окт '19 4:22) logic

@logic: пусть множество A перечислимо в используемом мной смысле, то есть его можно напечатать. Это, как я говорил, формально означает, что A или пусто, или есть множество значений тотальной вычислимой функции.

Теперь надо доказать, что перечислимые множества -- это в точности области определений частичных вычислимых функций (то есть множество всех x, для которых f(x) определено, что равноценно остановке программы ф_q, вычисляющей f). В одну сторону: если A можно напечатать, то f дожидается появления на печати поданного на вход числа x.

(27 Окт '19 5:48) falcao

(продолжение) В другую: перебираем все пары (x,n), заставляем программу f на входе x работать n шагов. Если произошла остановка, печатаем число x.

(27 Окт '19 5:49) falcao

Я сейчас осознал, что опечатка, по моему мнению присутствующая в ответе, не является настолько невинной, насколько я предполагал. В предпоследнем абзаце Вы говорите "Если M за это время остановилась, программа что-то выдаёт в качестве результата" и потом "Если же за время <=x машина M остановилась, мы загоняем нашу программу в бесконечный цикл", то есть в одной и той же ситуации происходит 2 разных события. Я думал, что во второй цитате Вы имеете в виду "Если же за время <=x машина M не остановилась..." Но тогда условие из начала последнего абзаца не выполняется.

(27 Окт '19 8:41) logic

(продолжение) Если же опечатка в первой цитате, и она должна быть "Если M за это время не остановилась, программа что-то выдаёт", то непонятно, как это сделать, потому что если программа не остановилась, то при реализации проверки остановки М с помощью Т-предиката Клини, упомянутого мной в другом вопросе ( https://fastpic.ru/view/90/2019/1027/d6db42e281dc4a5a02a33d2e94274468.png.html ) программа будет бесконечно искать этот z, и она никогда не остановится, так что не получится "что-то выдать"

(27 Окт '19 8:45) logic

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

Тут сама конструкция очень простая, и, если идти от смысла, то всё сразу должно стать ясно.

(27 Окт '19 14:20) falcao
показано 5 из 13 показать еще 8
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×33

задан
26 Окт '19 22:38

показан
371 раз

обновлен
27 Окт '19 14:20

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

по почте:

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

по RSS:

Ответы

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

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