آلات Turing: هل يمكن للآلة الكتابة بعدد محدود من خلايا الذاكرة، ولكن ليس توقف؟
-
29-09-2020 - |
سؤال
أحاول تقليل مشكلة وقف إظهار مشكلة أخرى غير قابلة للكشف.تنطوي المشكلة على برنامج صحيح إذا كان الجهاز $ m $ يكتب إلى كمية تعسفية من الذاكرة، و False إذا كتبت إلى كمية محدودة من خلايا الذاكرة.أفكر الآن، يكتب إلى كمية محدودة من خلايا الذاكرة المكافئة لوقف، أو هل يمكن أن تكون هناك حالات تكتب فيها الآلة كمية محدودة من خلايا الذاكرة دون وقف؟
شكرا لك مقدما!
المحلول
النظر في آلة تورينج تتحرك مرارا وتكرارا رأسها الصحيح، ثم غادر، ثم اليمين، ثم اليسار، وهلم جرا.
لا تنتمي إلى cs.stackexchange