¿Turing reducible en números naturales?

Question

Estoy confundido acerca de Turing Cosas reducibles.

Entendí a Turing Reducible como este

"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"

Entonces, por esto, tengo que resolver el problema.

n es el conjunto de números naturales= {1, 2, 3, ...}

Deja que sea el conjunto de todos los números aún naturales.

Sea B el conjunto de todos los números naturales extraños.

Demuestra que A está reducible a B.

Aquí es lo que he pensado.

El algoritmo de Oracle de A es n% 2== 0 que n pertenece a números naturales.

y el algoritmo de Oracle de B es n% 2== 1 que n pertenece a números naturales.

¿Cómo puedo derivar n% 2== 0 de n% 2== 1?

o mi enfoque es incorrecto?

Gracias por su ayuda.

Answer 1

Para demostrar que $ a $ está turing-reducible a $ b $ necesita probar el existencia de una máquina de Turing que puede decidir $ a $ cuando se le da acceso a un oráculo para $ b $ .

En su caso específico, una posible máquina de Turing $ m $ toma como entrada una cadena $ x \ in \ {0 , 1 \} ^ * $ codificando el número natural $ n $ (estoy asumiendo $ 0 \ en \ mathbb {n} $ ) en binario y funciona de la siguiente manera:

• voltea el último bit de $ x $ . Ahora $ x $ representa un número impar IFF el número de entrada $ n $ fue incluso.
• invoca el oráculo para $ b $ con entrada $ x $ .
.
• Acepta IFF, según el Oracle, $ x \ en b $ .

Observe que el hecho de que $ m $ tiene acceso a un oráculo para $ b $ no Significa que $ m $ debe usar ese oráculo. La siguiente es también una opción válida para $ m $ :

• Localice el último bit $ y $ de la cadena de entrada $ x $ .
• si $ y= 0 $ Aceptar. De lo contrario rechazar.