Сокращение от Atm до A (по моему выбору) и от A до Atm - PullRequest
Новая
       40

Сокращение от Atm до A (по моему выбору) и от A до Atm

2 голосов
/ 28 февраля 2012

Сокращение многих, не симметрично.Я пытаюсь доказать это, но это не так хорошо работает.

Учитывая два языка A и B, где A определяется как 

A={w| |w| is even} , i.e. `w` has an even length

и B=A_TM, где A_TMнеразрешима, но узнаваема по Тьюрингу!

С учетом следующего сокращения: 

f(w) = { (P(x):{accept;}),epsilon    , if |w| is even
f(w) = { (P(x):{reject;}),epsilon    , else

(пожалуйста, прости меня за то, что я не использую латекс, у меня нет с ним опыта)

Как я вижу, сокращение отA <= B (от A до A_TM) возможно и прекрасно работает.Однако я не понимаю, почему B <= A, невозможно.</p>

Не могли бы вы уточнить и объяснить?

Спасибо, Рон

1 Ответ

3 голосов
/ 28 февраля 2012

Предположим на минуту, что B <= A. Тогда есть функция f:Sigma*->Sigma* такая, что: 

f(w) = x in A           if w is in B
     = x not in A       if w is not in B

Следовательно, мы можем описать следующий алгоритм [машина Тьюринга] M на входе w: 

1. w' <- f(w)
2. if |w'| is even return true
3. return false

Легко доказать, что M принимает w тогда и только тогда, когда w находится в B [оставлено как упражнение для читателя], таким образом L(M) = B.
Кроме того, M останавливается для любого входа w [из его конструкции]. Таким образом - L (M) разрешима.

Но мы поняли, что L(M) = B решаемо - и это противоречие, потому что B = A_TM неразрешимо!

...