تورينج قابلة للاختزال في الأعداد الطبيعية؟

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==0 من n%2==1 ؟

أم أن أسلوبي خاطئ؟

شكرا لمساعدتك.

Answer 1

لعرض ذلك $أ$ هو تورينج قابل للاختزال إلى $ب$ تحتاج إلى إثبات وجود آلة تورينج قادرة على اتخاذ القرار $أ$ عند منح الوصول إلى أوراكل ل $ب$.

في حالتك المحددة، آلة تورينج محتملة $م$ يأخذ كمدخل سلسلة $x \في \{0,1\}^*$ ترميز العدد الطبيعي $ن$ (أنا أفترض $0 \in \mathbb{N}$) في ثنائي ويعمل على النحو التالي:

• فإنه يقلب الجزء الأخير من $x$.الآن $x$ يمثل رقمًا فرديًا إذا كان رقم الإدخال $ن$ كان حتى.
• إنه يستدعي أوراكل ل $ب$ مع المدخلات $x$.
• فإنه يقبل إذا، وفقا لأوراكل، $x \في B$.

لاحظ أن حقيقة ذلك $م$ لديه حق الوصول إلى أوراكل ل $ب$ لا يعني ذلك $م$ يجب أن تستخدم تلك أوراكل.ما يلي هو أيضًا اختيار صالح لـ $م$:

• تحديد موقع الجزء الأخير $ص$ من سلسلة الإدخال $x$.
• لو $ص=0$ يقبل.وإلا رفض.