Пусть T = {<M> | M - это TM, который принимает $ w ^ R $ всякий раз, когда принимает w}. Покажите, что Т неразрешима - PullRequest
Новая
       120

Пусть T = {<M> | M - это TM, который принимает $ w ^ R $ всякий раз, когда принимает w}. Покажите, что Т неразрешима

0 голосов
/ 29 апреля 2018

Пусть T = { | M - это TM, который принимает w r всякий раз, когда принимает w}.
Покажите, что T неразрешимо.

У меня есть два ответа на этот вопрос - Сан-Диего :

5,9
Пусть T = { | M - это TM, который принимает w r всякий раз, когда принимает w}.

Предположим, что T разрешимо, и пусть решающий R решит T. Уменьшите значение A TM , построив TM S следующим образом:

  • S: на входе
    1. создайте TM Q следующим образом:
      На входе х:
      1. если x не имеет формы 01 или 10 отклонить.
      2. если x имеет форму 01, то примите.
      3. else (x имеет форму 10), запустите M на w и примите, если M принимает w.
    2. Запустить R на
    3. Принять, если R принимает, отклонить, если R отклоняет.

Поскольку S принимает решение A TM , о котором известно, что оно неразрешимо, мы знаем, что T не разрешимо

нераскрытый источник:

  • 5.12 Покажем, что A TM ≤ m S путем отображения ‹ M , w ›до‹ M ' ›где M' является следующим ТМ:

    • M ' = «На входе x :
      1. Если x = 01, то принять .
      2. Если x ≠ 10, то отклонить .
      3. Если x = 10, имитировать M на w .
        Если M принимает w , тогда принимает ; если M останавливается и отклоняется, тогда отклоняет . ”

    Если ‹ M , w › ∈ A TM , то M принимает w и L ( M ') = {01,10}, поэтому ‹ M' › ∈ S .
    И наоборот, если ‹ M , w › ∉ A TM , то L ( M ') = {01}, поэтому ‹ M '› ∉ S . Таким образом,
    ‹ M , w › ∈ A TM ⇔ ‹ M '› ∈ S .

Но я не понимаю следующее:

1- какова связь между x и w?

2- почему мы рассматриваем 2 случая ‹ M , w › ∈ A TM и ‹ M , ш ›∉ А ТМ ?

3- почему если A отображаемо сводимо к S, это делает S неразрешимым?

Кто-нибудь может прояснить мне эти моменты?

1 Ответ

0 голосов
/ 09 мая 2018

Я думаю, что это не подходит для того, чтобы спрашивать в SO, потому что это не образовательный сайт, но я ответил на него.

1- какова связь между x и w?

Ответ 1: x - это символ, который используется для использования символа для работы. Этот символ не должен быть в алфавите языка, просто он. Не имеет любое отношение к ш.

2- почему мы рассматриваем 2 случая ‹M, w› ∈ ATM и ‹M, w› ∉ ATM?

Ответ 2: Для проверки того, что язык типа L является разрешимым или нет, нам нужно определить строку, в которой w является членом языка или нет. Итак, мы нужно рассмотреть два типа строки w∉L и w∈L.

3- почему, если отображение отображаемо к S, это делает S неразрешимым?

Ответ 3: Это означает, что процесс проверки строки на языке A и S аналогичен, и если мы не можем найти алгоритм проверки это для A, мы не можем найти алгоритм для S.

...