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

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

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

הגדרות

הגדרה: נאמר ש$L_{R}\in R$ מפרידה רקורסיבית את השפות $L_{1},L_{2}$, אם: $L_{1}\cap L_{R}=\emptyset$ $L_{2}\subseteq L_{R}$

הגדרה: נאמר שהשפות $L_{1},L_{2}$ נתנות להפרדה רקורסיבית אם"ם קיימת שפה כריעה $L_{R}$ המפרידה אותן.

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

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

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

נגדיר את השפה $L_{1}$ באופן דומה לשפת האלכסון:

$L_{1}=\{\langle M\rangle \mid M(\langle M\rangle )={\text{accept}}\}$

ואת $L_{2}$ כ"משלימתה"

$L_{2}=\{\langle M\rangle \mid M(\langle M\rangle )={\text{reject}}\}$

(נשים לב שייתכן ש$L_{1}\cup L_{2}\neq \Sigma ^{*}$, מפני שישנן שפות שהפעלתן על קידודיהן אינה מסתיימת כלל, ולכן אין מדובר ממש בשפה משלימה).

טענה: $L_{1}$ ו$L_{2}$ אינן נתנות להפרדה רקורסיבית.

הוכחה: צורת ההוכחה מזכירה מעט את זו שבעיית העצירה אינה כריעה.

נניח על דרך השלילה שקיימת שפה $L_{R}$ המפרידה בין השפות, ונניח ש $M$ היא מ"ט המכריעה שפה זו. מה ערכה של $M(\langle M\rangle )$?

1. אם ערכה הוא accept, אז לפי ההגדרת $L_{1}$, $\langle M\rangle \in L_{1}$. מצד שני, המ״ט מכריעה את $L_{R}$ ולכן נובע $\langle M\rangle \in L_{R}$, אך זו סתירה כי $L_{1}\cap L_{R}=\emptyset$.
2. באותו אופן, אם ערכה הוא reject, אז לפי ההגדרת השפה $L_{2}$, $\langle M\rangle \in L_{2}$,ומכיוון ש־$L_{2}$ מוכלת ב־$L_{R}$, גם $\langle M\rangle \in L_{R}$, וזו סתירה כי המ״ט שמכריעה את $L_{R}$ ענתה בדחיה.

הפרק הקודם: משפט רייס

אי-הפרדתיות רקורסיבית

הפרק הבא: משפט הרקורסיה