حجم تقاطع 2 اللغات حجم ليس حلول

Question

أعتقد أن اللغة التالية ليست حلولة ولكن لا يمكنني التفكير في التخفيضات لإظهارها. سأكون ممتنا بعض التلميحات أو الحدس

$ eq= $ { $ $ | $ M1 \، \، \، \، \، \، \، M2 \، \، \، \، \، \، \، TMS \، \، \، و \ \ \ \ \ |L (M1) \، ∩ \، l (m2) \، | \، $$= 2020 \، $ }

Answer 1

النظر في مثيل وقف المشكلة $ \ langle m، x \ rangle $ . بناء آلة تورينج جديدة والتي $ m_x $ والتي تقبل السلاسل $ 0 $ ، $ 00 $ " span class="حاوية الرياضيات"> 000 $ \ Ldots 0 ^ {2020} $ إذا كان الجهاز $ m $ توقف على المدخلات $ x $ ؛ وسوف يرفض كل السلاسل الأخرى. دع $ m_u $ يكون tm الذي يقبل جميع الأوتار.

اقنع نفسك أن $ | l (m_x) \ cap l (m_u) | $ سيكون 2020 إذا $ m $ توقف على $ x $ ، وإلا $ 0 $ .

يتبع دليل بسهولة.

(غير رسمي) تلميح: كلما كان لديك مثل هذا السؤال، حاول التفكير في كيفية حل مشكلة وقف (أو بعض اللغات الأخرى التي لا يمكن تعويضها) باستخدام الافتراضية decider للغة المحددة.

Answer 2

welcome to the site :)

I assume you already know that the Halting problem $L_H$ is undecidable (as it is usually the first specific undecidable language students learn of). So, let us try and find a reduction $L_H \leq EQ$.

We want to know whether some given TM $M$ halts given the input word $w$ by transforming the pair $\langle M, w \rangle$ to some $EQ$-instance $f(\langle M, w \rangle) = \langle M_1, M_2 \rangle$ such that $\langle M, w \rangle \in L_H$ if and only if $\langle M_1, M_2 \rangle \in EQ$. Let us consider some dummy TM $M_{2020}$ which just accepts 2020 inputs (any set of 2020 words will do the trick) and modify $M_{2020}$ such that it only ever accepts if $M$ halts on $w$ to get another TM $M_{2020}(M, w)$. Since we know $M$ and $w$ when we construct $M_{2020}(M, w)$, we can implement it to do the following:

1. Read the input and if it is one of the 2020 words accepted by $M_{2020}$, make note of that (we can use the states to store this).
2. Clear the tape and write $w$ to it.
3. Run $M$ on $w$.
4. If $M$ halts on $w$, accept the original input.

Such a construction can be performed by another TM, this is a bit tedious to show formally but by noting that we can essentially "embed" $M$ in $M_{2020}(M, w)$ it should be intuitive that this can be done (as $M_{2020}$ is a fixed TM).

Now observe that $M_{2020}(M, w)$ accepts some input $x \in L(M_{2020})$ precisely when $M$ halts on $w$, hence we have that $L(M_{2020}) = L(M_{2020}(M, w))$ if and only if $\langle M, w \rangle \in L_H$, otherwise we have $L(M_{2020}(M, w)) = \emptyset$. It follows that $$ | L(M_{2020}(M, w)) \cap L(M_{2020}) | = \begin{cases} 2020, & \text{if $M$ halts on $w$} \\ 0, & \text{otherwise} \end{cases} $$ and thus (denoting $\langle M_{2020}, M_{2020}(M, w) \rangle$ as $f(\langle M, w \rangle$) we have $\langle M, w \rangle \in L_H \Leftrightarrow f(\langle M, w \rangle)$ and therefore a suitable reduction.

An easier way to prove that the language is not decidable is by using Rice's theorem which (roughly speaking) says that properties of functions computed by TMs (we call these semantic properties) cannot be decided algorithmically unless they are trivial. If we fix some TM $M_1$ and consider an arbitrary TM $M$ then asking whether $L(M_1) \cap L(M)$ has size 2020 is such a semantic property and hence Rice's theorem immediately gives us that $EQ$ is undecidable. The theorem (for me, at least) is basically the formal underpinning of the informal intuition I gave above.