تثبت undecidability للغة الذي يحتوي على سلسلة مع بعض بناء الجملة

Question

دعونا نقول لدينا المشكلة التالية:

$$\mathcal{L}_1 = \{\langle \mathcal{M} angle | \mathcal{M}\ ext{هو آلة تورينج دولار\mathcal{L}(\mathcal{M})$ يحتوي على سلسلة مع ثلاثة أصفار}\}$$

نود أن نثبت أن $\mathcal{L}_1$ هو غير مقرر.أنا عموما استخدام الأرز نظرية إثبات أن اللغة غير مقرر ، ولكن في هذه الحالة نحن لا نتعامل مع الدلالي الملكية اللغة وإنما بناء الجملة.في الحالات التي يجب أن تثبت على أساس لغة البناء ، كيف أن هذه العملية تبدو وكأنها تختلف من تثبت مع الأرز نظرية?

Answer 1

فإنه يمكن التفكير الدلالي الملكية اللغة ، طيب استخدام الأرز نظرية هنا.

تعريف $C=\{L| ext{هناك سلسلة بالضبط 3 أصفار في }ل\}$

لذلك ، $L_1=\{<M>|M ext{ هو آلة تورينج و } ل(م)\C\}$ و لأن $ج eq\emptyset$ و $C$ ليست كل اللغة ثم الأرز نظرية ، $L_1\لافي R$.