Докажите, что множество $%\{\langle a,b\rangle:\phi_a()\text{ и } \phi_b()\text{ определены и равны}\}$% является областью определения функции $%\phi_c$% для некоторой программы $%c$%.

То есть что $%\{\langle a,b\rangle:\phi_a()\text{ и } \phi_b()\text{ определены и равны}\}=\{x:\phi_c(x)\text{ останавливается}\}$%

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

1

На уровне идеи: перебираем все тройки вида (a,b,n). Для данной тройки прогоняем на n шагов программы a и b. Если обе остановились и выдали одно и то же значение, печатаем номер пары (a,b). Это значит, что множество таких пар рекурсивно перечислимо.

Второе описание равносильно первому (оно разве что чуть более искусственно и чуть менее стандартно). Есть перечисляющая процедура для множества; параллельно действует программа c, которой на вход подают объект x, и она выполняет действия перечисляющей программы, следя за появлением x на печати. В этот момент c останавливается.

(26 Окт '19 23:10) falcao

Но ведь ф_а() может остановиться за 13 шагов и выдать 1, а ф_б() - за 28 шагов и тоже выдать 1. В таком случае тем не менее мы имеем ф_а()=ф_б(). Но Ваш алгоритм проверяет, равны ли программы после n шагов для каждого n. То есть если я его правильно понимаю, он не учитывает, что программы могут остановиться и выдать то же самое значение за разное количество шагов. Или учитывает?

(27 Окт '19 3:38) logic

Кроме того, если в программе а всего одна инструкция (скажем ф_а() останавливается после первого шага и выдает 1), а в программе b 50 инструкций (ф_б() останавливается через 50 шагов и выдает 1), то Ваш алгоритм после проверки тройки (a,b,1) перейдет к проверке тройки (a,b,2), и частью этой проверки является проверка того, что выдаст "кусок" программы а, состоящий из первых двух инструкций программы а, после того как этот кусок запустить на пустом аргументе. Но в программе а всего одна инструкция, так что непонятно, что в этом случае будет делать алгоритм.

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

@logic: число шагов работы программ не имеет значения. Если a останавливается на шаге n1, а b на шаге n2, то при n=max(n1,n2) мы увидим, что обе машины остановились, и тогда пару (a,b) напечатаем. Важно только то, что n может принимать любые значения.

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

А зачем вообще надо прогонять программу на n шагов, а не всю сразу?

То есть почему нельзя воспользоваться Т-предикатом Клини, т.е. теоремой https://i87.fastpic.ru/big/2019/1027/53/42655c2269962d8007df35a8056f7453.png (а точнее - этой версией https://i90.fastpic.ru/big/2019/1027/68/d6db42e281dc4a5a02a33d2e94274468.png ) следующим образом:

Программа с берет на вход число t=п(а,б), разбивает его на а и б, и для каждого натурального z проверяет, верно ли T^0(a,z). Если его не существует, то программа с работает вечно. (продолжение следует....)

(27 Окт '19 7:11) logic

(продолжение) Если же такое z существует, то программа с запоминает чему равно upshot(z) и снова проверяет для каждого натурального z', верно ли T^0(b,z). Если такого z' не существует, то программа работает вечно. Если оно существует, то программа смотрит на upshot(z') и проверят, равны ли upshot(z) и upshot(z'). Если равны, то она выдает 1. Если нет, то она уходит в бесконечную петлю.

(27 Окт '19 7:12) logic

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

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

Ваш ответ

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

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

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

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

отмечен:

×32

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

показан
321 раз

обновлен
27 Окт '19 15:54

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

по почте:

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

по RSS:

Ответы

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

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