チューリングは自然数で約分可能ですか?

Question

チューリング還元可能なことについて混乱しています。

チューリング還元可能はこう理解しました

"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 が B にチューリング還元可能であることを証明します。

これが私が考えたことです。

A のオラクル アルゴリズムは n%2==0 であり、n は自然数に属します。

そして、B のオラクルアルゴリズムは n%2==1 であり、n は自然数に属します。

n%2==1 から n%2==0 を導出するにはどうすればよいですか?

それとも私のアプローチが間違っているのでしょうか？

ご協力いただきありがとうございます。

Answer 1

それを示すために $A$ チューリング還元可能である $B$ を決定できるチューリングマシンの存在を証明する必要があります。 $A$ オラクルへのアクセスが与えられたとき $B$.

あなたの特定のケースでは、考えられるチューリングマシン $M$ 文字列を入力として受け取ります $x \in \{0,1\}^*$ 自然数のエンコード $n$ (私は仮定しています $0 \in \mathbb{N}$) バイナリで次のように動作します。

• 最後のビットを反転します $x$. 。今 $x$ 入力された数値の場合は奇数を表します $n$ 均等だった。
• それはオラクルを呼び出します $B$ 入力あり $x$.
• 神託によると、それは受け入れられます。 $x \in B$.

という事実に注目してください。 $M$ オラクルにアクセスできる $B$ という意味ではありません $M$ その神託を使わなければなりません。以下も有効な選択肢です $M$:

• 最後のビットを見つけます $y$ 入力文字列の $x$.
• もし $y=0$ 受け入れる。それ以外の場合は拒否します。