תורת החישוביות/כריעות שפות/אי-הפרדתיות רקורסיבית

נניח שברשותנו שפה כלשהי, L. אם נרחיב אותה מספיק, בוודאי שנגיע בשלב כלשהו לשפה כריעה. ככלות הכל, כל שפה L מקיימת $L\subseteq {\mathrm{\Sigma }}^{*}$, ו${\mathrm{\Sigma }}^{*}\in R$ היא בודאי שפה כריעה (ע״י מ״ט שבצעד הראשון עוברת למצב מקבל). הדבר מעלה את השאלה הבאה. נניח שיש שתי שפות זרות, $L_1$ ו$L_2$. האם אפשר להרחיב את $L_2$ לשפה כריעה $R^{\prime }$, מבלי להשתמש במילים מ־$L_1$, כלומר ש־$L_1$ ו־$R^{\prime }$ תהינה זרות זו לזו?

כעת נראה שישנן שפות שאי אפשר להפריד אותן כך.

הגדרות

נשים לב שהמושג "נתנות להפרדה רקורסיבית" אכן סימטרי. אם"ם $L_1$ ו$L_2$ נתנות להפרדה רקורסיבית, כך גם $L_2$ ו$L_1$. נניח שישנה שפה רקורסיבית $L_R$ המכילה את $L_2$ והזרה ל$L_1$. נגדיר את $\overline{L_R}={\mathrm{\Sigma }}^{*}\setminus L_R$, ונשים לב ש$\overline{L_R}$ גם היא כריעה, וכן שהיא מכילה את $L_1$ וזרה ל$L_2$.

דוגמה: אי הפרדתיות שפת האלכסון מ"משלימתה"

נראה כעת דוגמה לשפות שאינן נתנות להפרדה רקורסיבית.

נגדיר את השפה $L_1$ באופן דומה לשפת האלכסון:

$L_1=\{⟨M⟩\mid M(⟨M⟩)=\text{accept}\}$

ואת $L_2$ כ"משלימתה"

$L_2=\{⟨M⟩\mid M(⟨M⟩)=\text{reject}\}$

(נשים לב שייתכן ש$L_1\cup L_2\ne {\mathrm{\Sigma }}^{*}$, מפני שישנן שפות שהפעלתן על קידודיהן אינה מסתיימת כלל, ולכן אין מדובר ממש בשפה משלימה).

תבנית:תורת החישוביות