إثبات وجود TM الذي يقبل اللغة التالية

Question

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

$ l_k={ |\، م \، \، \، \، \، \، \، A \، TM \، \، هذا \، \، يستخدم \، \، في \، \، معظم \ \، k \، \، الشريط\، \، الخلايا \ \، \، \، متى \، \، \، تشغيل \، \، \، ON \، \، \، \ EPSILON \} $

أثبت ذلك: $ l ^ *=bigcup \ limits_ {k \، \ on \، \ mathbb {n}} l_k \، \ in \، \، \، re \ setminus r $

Answer 1

اللغة $ l ^ * $ يتكون من جميع أجهزة Turing $ m $ والتي تتوقف في النهايةأو كرر التكوين.لكل جهاز $ m $ ، من خلال محاكاة الجهاز، يمكنك بسهولة ملاحظة أن إحدى هذه الإمكانيات قد حدث.