لماذا تسقط مشكلة وقف لغات GOTO محدودة على أعلى قيمة الثوابت والمتغيرات؟

Question

مأخوذ من امتحان قديم لجعلتي التي أستخدمها لإعداد نفسي لامتحان قادمة:

المعطى هي لغة $ \ text {goto} _ {17} ^ c \ subseteq \ text {goto} $ . تحتوي هذه اللغة بالضبط تلك $ \ text {goto} $ غير ثابتة أعلاه $ 17 $ ولا أي متغير على الإطلاق أعلاه $ C $ .

$ goto $ هنا يصف مجموعة من جميع البرامج المكتوبة في $ goto $ language العناصر التالية:

مع المتغيرات $ v_i \ in \ mathbb {n} $ الثوابت $ c \ in \ mathbb {n}
المهمة: $ x_i:= c، x_i:= x_i \ pm c $
القفز الشرطي: إذا (مقارنة) Goto $ l_i $
Haltcommand: توقف

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

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

هل هذا صحيح؟ علاوة على ذلك، كيف ستبدو دليلا أكثر رسمية إذا كان؟ إذا لم يكن كذلك، فكيف مظهر دليل صحيح؟

Answer 1

هناك عدد محدود من الدول المختلفة (مجموعة قيم المتغيرات وعداد البرنامج).لديك "برامج GOTO المحدودة" هي مجرد طريقة (فوضوي) لوصف Automaton المحدد المحدد.

أو مجرد سبب أن البرنامج ينص على كونه محددا، من الممكن بالتأكيد تعيين جميع الحسابات غير المحتملة غير المحتملة (من قبل شيء مثل عملية اتساع أول بحث في الرسم البياني للولايات والجيران).