자연수에서 줄이는 튜닝 가능?

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, ...}

집합입니다.

자연 숫자의 모든 세트가되도록하십시오.

b는 모든 이상한 자연 숫자의 집합을하자.

는 A가 b. b.

여기에 내가 생각한 것입니다.

a의 Oracle 알고리즘은 N % 2== 0이 자연수에 속합니다.

및 B의 Oracle 알고리즘은 N % 2== 1이 N 자연수에 속합니다.

어떻게 n % 2== 0에서 n % 2== 1?

을 어떻게 도출 할 수 있습니까?

또는 내 접근 방식이 틀렸어?

도움을 주셔서 감사합니다.

Answer 1

$ a $ 이 $ b $ 에 튜닝 가능됨을 보여줍니다. $ a $ 을 결정할 수있는 튜핑 머신의 존재 "> $ b $ .

특정 경우 $ m $ 은 문자열 $ x \ in \ {0 , 1 \} ^ * $ 자연 숫자 $ n $ (나는 $ 0 \ in \ mathbb {n} $ ) 바이너리에서 다음과 같이 작동합니다.

• $ x $ 의 마지막 비트를 뒤집습니다. 이제 $ x $ 은 홀수 숫자 $ n $ 님이
• 입력 $ x $ 을 사용하여 $ b $ 에 대한 오라클을 호출합니다.
• Oracle, $ x \ in b $
에 따르면 IFF를 수용합니다.

$ m $ 이 $ m $ 은 오라클을 사용해야합니다. 다음은 $ M $ :

에 대한 유효한 선택 사항이기도합니다.

• 입력 문자열 $ x $ 의 마지막 비트 $ y $ 을 찾습니다.
$ y= 0 $ 수락하는 경우. 그렇지 않으면 거부합니다.