تورينج قابلة للاختزال في الأعداد الطبيعية؟
-
29-09-2020 - |
سؤال
أنا في حيرة من أمري بشأن أشياء تورينج القابلة للاختزال.
لقد فهمت تورينج قابل للاختزال مثل هذا
"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 ؟
أم أن أسلوبي خاطئ؟
شكرا لمساعدتك.
المحلول
لعرض ذلك $أ$ هو تورينج قابل للاختزال إلى $ب$ تحتاج إلى إثبات وجود آلة تورينج قادرة على اتخاذ القرار $أ$ عند منح الوصول إلى أوراكل ل $ب$.
في حالتك المحددة، آلة تورينج محتملة $م$ يأخذ كمدخل سلسلة $x \في \{0,1\}^*$ ترميز العدد الطبيعي $ن$ (أنا أفترض $0 \in \mathbb{N}$) في ثنائي ويعمل على النحو التالي:
- فإنه يقلب الجزء الأخير من $x$.الآن $x$ يمثل رقمًا فرديًا إذا كان رقم الإدخال $ن$ كان حتى.
- إنه يستدعي أوراكل ل $ب$ مع المدخلات $x$.
- فإنه يقبل إذا، وفقا لأوراكل، $x \في B$.
لاحظ أن حقيقة ذلك $م$ لديه حق الوصول إلى أوراكل ل $ب$ لا يعني ذلك $م$ يجب أن تستخدم تلك أوراكل.ما يلي هو أيضًا اختيار صالح لـ $م$:
- تحديد موقع الجزء الأخير $ص$ من سلسلة الإدخال $x$.
- لو $ص=0$ يقبل.وإلا رفض.