لماذا هذا آلة تورينج غير صالحة؟

Question

أثناء القيام بمراجعة الامتحان أواجه مشكلة في الإجابة على السؤال التالي من الكتاب، "مقدمة لنظرية الحساب" بواسطة Sipser. لسوء الحظ، لا يوجد حل لهذا السؤال في الكتاب.

اشرح لماذا لا يوجد ما هو آلة تورينج مشروعة.

م = {

الإدخال عبارة عن متعدد الحدود P أكثر من المتغيرات X1، ...، XN

1. جرب جميع الإعدادات الممكنة من X1، ...، XN إلى القيم الصحيحة
2. تقييم P على كل هذه الإعدادات
3. إذا كانت أي من هذه الإعدادات تقيم إلى 0، اقبل؛ رفض خلاف ذلك. }

هذا يقودني للجنون! أظن أنه لأن مجموعة الأعداد الصحيحة غير محدودة؟ هل يتجاوز هذا بطريقة أو بأخرى حجم الأبجدية المسموح به؟

Answer 1

على الرغم من أن هذه طريقة غير رسمية تماما لوصف آلة Turing، إلا أنني أقول إن المشكلة هي واحدة مما يلي:

• otherwise reject - أنا أتفق مع welbog على ذلك. نظرا لأن لديك مجموعة لا حصر لها لا حصر لها، فلا يمكن أن يعرف الجهاز أبدا ما إذا كان الإعداد الذي يقيم عليه إلى 0 لا يزال سيأتي، وسيتم حله إلى الأبد إذا لم يتم العثور على أي - فقط عند مواجهة مثل هذا الإعداد، قد تتوقف الجهاز. هذا البيان الأخير عديم الفائدة ولن يكون صحيحا أبدا، ما لم يكن بالطبع تحد من الجهاز إلى مجموعة محدودة من الأعداد الصحيحة.

• ترتيب التعليمات البرمجية: أود أن أقرأ هذا pseudoodocode ك "أولا اكتب جميع الإعدادات الممكنة أسفل، ثم تقييم P على كل واحد" وهناك مشكلتك: مرة أخرى، من خلال وجود مجموعة لا حصر لها من الإعدادات الممكنة، ولا حتى الجزء الأول سينتهي من أي وقت مضى، نظرا لعدم وجود إعداد أخير أبدا والاستمرار في الخطوة التالية. في هذه الحالة، لا يمكن أن يقول الجهاز أبدا "لا يوجد 0 إعداد"، لكن لا يمكن إلا أن تبدأ في التقييم للعثور على واحدة. هذا، أيضا، سيتم حلها عن طريق الحد من مجموعة عدد صحيح.

على أي حال، لا أعتقد أن المشكلة هي حجم الأبجدية. لن تستخدم الأبجدية اللانهائية نظرا لأن الأعداد الصحيحة يمكن كتابةها في عشري / ثنائي / إلخ، وأولئك يستخدمون الأبجدية المحددة فقط (جدا).

Answer 2

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

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

Answer 3

أعتقد أن المشكلة هي مع الجزء الأخير جدا: otherwise reject.

وفق أساسيات مجموعة عد, ، أي مساحة متجه عبر مجموعة قابلة للعد هي تعداد نفسها. في حالتك، لديك مساحة متجهية فوق أعداد صحيحة الحجم n, ، والذي يعد. لذلك مجموعة من الأعداد الصحيحة تعد قابلة للعد، وبالتالي فمن الممكن تجربة كل مزيج منهم. (هذا هو القول دون أن تفتقد أي مزيج.)

أيضا، الحوسبة نتيجة p في مجموعة معينة من المدخلات أمر ممكن أيضا.

وإدخال حالة قبول عندما p يقيم إلى 0 هو ممكن أيضا.

ومع ذلك، نظرا لأن هناك عدد لا حصر له من ناقلات المدخلات، يمكنك أبدا رفض المدخلات. لذلك لا توجد آلة تورينج يمكن أن تتبع جميع القواعد المحددة في السؤال. بدون تلك القاعدة الأخيرة، فمن الممكن.