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

Question

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

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

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 

(Пожалуйста, простите меня за неиспользование Latex, у меня нет опыта работы с ним)

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

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

Благодаря Рон

Answer 1

Предположим на минуту, что 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 не определено!