Снижение от банкомата до банкомата

Question

Есть ли сокращение от банкомата до банкомата?

Я слишком много думал об этом и не смог найти ответ.

Я знаю, что сокращение от ATM-дополнения до ATM невозможно, потому что если бы оно было, банкомат не был бы в RE. Но как я могу доказать / сделать наоборот?

Большое спасибо:)

Answer 1

Нет сокращения отображения от (A_TM)^c до A_TM. Чтобы увидеть это, обратите внимание, что A_TM распознается по Тьюрингу, поэтому, если (A_TM)^c ≤_m A_TM, мы бы имели, что (A_TM)^c было бы распознаваемым по Тьюрингу. Но это невозможно, поскольку мы знаем, что (A_TM)^c не распознаваемо по Тьюрингу, поскольку, если бы это было так,_TM может быть разрешимым (поскольку любой язык, распознаваемый по Тьюрингу и распознаваемый совместно по Тьюрингу, разрешим).

Однако наблюдается снижение по Тьюрингу с (A_TM)^c до A_TM. Просто вызовите подпрограмму для A_TM и верните противоположный результат.