Тьюринг сводится в естественных числах?

Question

Я путаю в замешательстве придумываемых вещей.

Я понял, что Turing United, как это

"There is an oracle algorithm which is about set A and when this algorithm is derived from oracle algorithm of set B, it is called A is Turing-reducible to B"

Так что к этому мне нужно решить проблему.

n - набор натуральных чисел= {1, 2, 3, ...}

Пусть A - набор всех даже натуральных чисел.

Пусть B набор всех нечетных натуральных чисел.

Докажете, что a - это резюмирование до б.

Вот то, что я подумал.

Алгоритм Oracle a n% 2== 0, который n принадлежит натуральным числам.

и алгоритм Oracle b ì n% 2== 1, который n принадлежит натуральным числам.

Как я могу получить n% 2== 0 от n% 2== 1?

или мой подход не так?

Спасибо за вашу помощь.

Answer 1

Чтобы показать, что $ a $ - это подразумеваемый для $ B $ Вам нужно доказать Наличие Turging Machine, которая может решить $ A $ При определении доступа к Oracle для $ B $ .

В вашем конкретном случае возможная машина Turging $ m $ принимает в качестве входной строки $ x \ in \ {0 , 1 \} ^ * $ Кодирование естественного числа $ n $ (я предполагаю, что $ 0 \ in \ mathbb {n} $ ) в двоичных данных и работает следующим образом:

.
• Он переворачивает последний бит $ x $ . Теперь $ x $ представляет собой нечетное число iff Номер ввода $ N $ был даже.
• это вызывает Oracle для $ b $ с входом $ x $ .
• Это принимает IFF, в соответствии с Oracle, $ x \ in b $ .

Обратите внимание, что тот факт, что $ m $ имеет доступ к Oracle для $ B $ не означает, что $ m $ должен использовать это Oracle. Ниже также является действительным выбором для $ m $ :

.
• Найдите последний бит $ y $ of входной строки $ x $ .
• Если $ y= 0 $ Принять. В противном случае отклоните.