مشاكل آلة تورينج العالمية

Question

إذا كان لدي جهاز ، اتصل به الجهاز 1 ، فهذا قادر على حل مشكلة: إنها مجرد آلة ، وليس في حد ذاتها آلة تورينج. يمكن أن يحل مشكلة واحدة محددة. إذا كان من الممكن حل هذه المشكلة بالضبط على آلة تورينج عالمية ، فهل أجهزتي الأصلية ، 1 ، آلة تورينج عالمية أيضًا؟

هذا لا يحتفظ بجميع المشكلات ، والتي تم بالفعل أن تكون مختلطة. هل هناك أي مشاكل لديها هذه الخاصية الموصوفة على الإطلاق؟ إذا كان هذا غير صحيح على الإطلاق ، فلماذا؟

هل يمكن لأي شخص أن يعطي مثالًا على حل مشكلة. إذا تم حل هذه المشكلة بواسطة الجهاز الأصلي الخاص بي ، 1 ، فمن المؤكد أن هذا جهاز تحول عالمي؟ أم لا توجد هذه المشكلة؟ إذا لم يكن موجودًا ، فلماذا؟

أنا مهتم جدًا ، لكن لا يمكنني معرفة ذلك ... شكرًا.

تحرير: جعل السؤال أكثر وضوحا.

Answer 1

تتمثل الهدف من جهاز الدوران العالمي (UTM) في أنه بالنسبة لأي آلة تورينج (TM) ، يمكنك أخذ هذا TM وإنشاء ترميز لها يصف تشغيل TM ويكون هذا الترميز يعمل على TM آخر.

UTM هو TM الذي لديه تعريف قوي بما فيه الكفاية بحيث يمكن إعادة كتابة أي تعريف TM آخر فيه.

فكر في UTM كمترجم فوري. TM هي مهمة محددة.

ما لم يكن TM أيضًا في فئة المترجمين الفوريين ، فهذا ليس UTM أيضًا. (لأن UTM هو أيضا TM مكلفة على وجه التحديد).

للإجابة على سؤالك الثاني: إذا كان بإمكانك إظهار أن UTM و TM متكافئان ، فقد أظهرت أن TM هو أيضًا UTM. للقيام بذلك ، يجب أن تكون قادرًا على إظهار كيفية تغيير برنامج مشفر لـ UTM إلى برنامج مكافئ لـ TM.

Answer 2

يمكن لآلة تورينج عالمية حل أي من فئة كبيرة من المشاكل.

إذا كان جهازك (1) يمكنه حل 1+1 ، فهذا لا يعني أنه يمكن أن يحل أي من الفئة الضخمة. لذلك قد لا يكون عالمي آلة تورينج.

Answer 3

يميز المنطقون بين الظروف "الكافية" و "القناصة". خذ ، على سبيل المثال ، الجملة

السماء زرقاء.

(دعنا نفترض أن هذا صحيح دائمًا). ما تعرفه الآن هو:

عندما تنظر إلى السماء ، ترى اللون الأزرق.

ماذا أنت لا تعرف هذا:

عندما ترى اللون الأزرق ، فأنت تنظر إلى السماء.

- قد تنظر أيضًا إلى سيارة جارك.

من الناحية المنطقية ، اللون الأزرق هو ضرورة بالنسبة للسماء ، لكنها ليست كافية.

وينطبق الشيء نفسه على حالتك: الجهاز (1) يحل مشكلتك ، لذلك فهي بالفعل مشكلة قابلة للحل. وبالتالي ، فإن القدرة على حل المشكلة هي أ ضرورة شرط UTM ، ولكن ليس كافيًا ، لأن UTM يجب أن يكون قادرًا على حلها أي مشكلة (هذا قابل للحل على الإطلاق) ، وليس فقط هذا واحد.

Answer 4

يمكن لآلة تورينج عالمية حل أي رمز يمكن لأي آلة تورينج محددة حلها.

لذلك يمكن لآلة تورينج العالمية (2) حل المشكلة التي تم تصميم آلة تورينج الأصلية (1) لحلها.

ومع ذلك ، يمكن أن تحل جهاز تورينج الأصلي الخاص بك (1) فقط هذه المشكلة الدقيقة ولا يمكنها حل أي مشكلة أخرى (بما في ذلك "مشكلة" كونها آلة تورينج عالمية).

لذلك لا ، آلة تورينج الأصلية الخاصة بك ليست آلة تورينج عالمية وفقا لوصفك. (قد يكون الأمر إذا حددته ، لكن هذا نوع من الغش).

Answer 5

هل يمكن لأي شخص أن يعطي مثالًا على حل مشكلة.

بالتأكيد: بالنظر إلى جهاز التحويل المشفر والبيانات ، ما هي النتيجة :) إذا كان جهازك يمكنه حل هذه المشكلة ، فهو بالتأكيد UTM.

هل تعرف خط التفكير لماذا هذه المشكلات المختلفة في NP؟ مثل "هل يمكنني حل مشكلة 3 سور عندما يكون لدي جهاز يحل مشكلة هاميلتون؟" يمكنك بالتأكيد استخدام نفس الشيء للإجابة على سؤالك.

Answer 6

إن إثبات اكتمال نظام معين ليس تافهاً ، إلا إذا كان بإمكانك إظهار أنه مكافئ/متساوي الشكل لنظام آخر يعرف أنه كامل. حتى إجابة قصيرة: لا يوجد اختبار بسيط يمكنك وضع جهازك للتحقق مما إذا كان Turing كاملًا أم لا. يجب عليك تحليل وإظهار خصائص النظام ككل.

إذا كنت ترغب في معرفة المزيد حول هذا الموضوع ، فاقرأ هذه المقالات عن اكتمال تورينج و نظرية القابلية للحساب.

Answer 7

تخيل UTM كما لو كنت ستنتقل إذا كان عليك كتابة رمز (مستوى عال) لمحاكاة آلة تورينج. ستتطلب ما يلي: 1.ray للاحتفاظ برموز الإدخال والأشياء التي سيفعلها Yiu عليها. 2. صفيف (ممكن 2-D) للاحتفاظ بوظيفة الانتقال التي ستطالب بها المستخدم. 3. خوارزمية تقرأ مدخلات المستخدم لوظائف الانتقال ومحاكاةها على المصفوفة 1. 4. متغيرات سيحتاج البرنامج إلى تتبع حالته الخاصة.

إذا كنت تفكر بهذه الطريقة ، إذا انتهى بك الأمر إلى الحصول على ملف رمز العمل تماما ينتهي بك الأمر مع UTM مثالي. ومع ذلك ، فإن الصيد لا يهم مدى كفاءتك في رمزك ، لا يمكنك منع المستخدم من إدخال وظائف الانتقال التي يمكن أن تتسبب في تشغيل الكود الخاص بك إلى الأبد. لذلك ستكون هناك بعض المشكلات التي ستفشل فيها UTM ، ثم نقول ذلك لهذه المشكلات لا يمكننا تطوير آلة اختبار العضوية. (على الرغم من أن إشعار آلة التحقق من العضوية ممكنة دائمًا)