הצגת המקור של הדף "תורת החישוביות/כריעות שפות/שפות שאינן כריעות/ארגז חול"

{{תורת החישוביות}}


ב[[תורת החישוביות/כריעות שפות#כריעות: מחלקות של שפות ותכונותיהן|חלקים הקודמים]] ראינו מספר קבוצות של שפות: 
R,
RE,
coRE, 
וכמובן, קבוצת העל
<math>\Sigma^*</math>.
בחלק זה נראה ש"תמונת העולם" נראית כבתרשים הבא.

[[File:RecursiveSets.png|הייחסים בין קבוצות השפות]]

כלומר,
* ישנן שפות ב<math>\Sigma^* \setminus RE</math>
* ישנן שפות ב<math>RE \setminus R</math>
* הקבוצה R הנה חתוך RE וcoRE (את זאת [[תורת החישוביות/כריעות שפות#כריעות: מחלקות של שפות ותכונותיהן|כבר ראינו]]).

==הקבוצה <math>\Sigma^* \setminus RE</math> איננה ריקה==

{{שקול לדלג|סיבה = חלק זה משתמש ב[[w:עוצמה (מתמטיקה)|עוצמות קבוצות]]. אפשר להבין את שאר החומר גם ללא חלק זה.}}

משיקולי מניה אפשר לראות שבהכרח יש שפות ב<math>\Sigma^* \setminus RE</math>.

ראשית נראה שיש יותר שפות ממחרוזות.
{{טענה|תוכן= 
יש יותר שפות ממחרוזות (או: קבוצת כלל המחרוזות מעל <math>\Sigma</math> היא בת-מניה, ואילו קבוצת כל השפות אינה בת-מניה). }}

{{הוכחה|1=
אפשר לראות שקבוצת השפות הנה קבוצת תתי הקבוצות של 
<math>\Sigma^*</math>,
שהיא כידוע <math>2^{\aleph_0}=\aleph</math>.

לחלופין, אפשר להוכיח ישירות שקבוצת השפות אינה בת-מניה באופן דומה ל[[w:האלכסון של קנטור|אלכסון של קנטור]].

נסמן את קבוצת כל המילים מעל <math>\Sigma</math> ב־x ונכתוב אותן לפי הסדר הלקסיקוגרפי:
<div class="mw-content-ltr"><math>x= \{ x_0, x_1, x_2, \ldots \}</math></div>
נניח בשלילה שקבוצת כל השפות היא בת מנייה, ונסמנה ב־A.
<div class="mw-content-ltr"><math>A=\{A_0, A_1, A_2, \ldots \}</math></div>

נגדיר את השפה D:
<div class="mw-content-ltr"><math>D=\{ x_i \mid x_i \notin A_i \}</math></div>
כלומר, אם המילה <math>x_0</math> נמצאת ב־<math>A_0</math> אז היא לא ב־D. אך אם אינה ב־<math>A_0</math>  אז היא כן תהיה ב־D.
ניתן לרשום זאת בצורת טבלה בה כל שורה היא אחת השפות <math>A_i</math> וכל עמודה היא אחת המילים <math>x_1</math> נסמן 1 אם <math>x_i \in A_i</math> ו־0 אחרת. 
<div class="mw-content-ltr"><math>
\begin{array}{c|cccc}
 & x_0 & x_1 & x_2 & \ldots \\
\hline
A_0 & \color{red}{1} & 0 & 1 & \\
A_1 & 0 & \color{red}{0} & 1 &  \\
A_2 & 1 & 0& \color{red}{1} & \\
\vdots &  & &  & \ddots
\end{array}
</math></div>
כעת נוכיח שהשפה D אינה אחת מהשפות <math>A_i</math>. נביט על האלכסון. אם עבור מילה מסויימת <math>x_i \in D</math> הרי שהיא אינה ב־<math>A_i</math>, ולכן <math>D \ne A_i</math>. למעשה – האלכסון מגדיר את <math>\overline D</math>.
}}

בעזרת הטענה הקודמת, אפשר לראות שבהכרח ישנן שפות ב<math>\Sigma^* \setminus RE</math>
{{הוכחה|1=
ההוכחה היא משיקולי ספירה. 
#מספר השפות בRE הוא לכל היותר מספר מ״ט השונות, כי כל מ״ט מגדירה שפה, ואם השפה ב־RE אז יש מ״ט שמקבלת כל מילה בה. מאידך, כמות מ״ט הקיימות הוא לכל היותר כמות המחרוזות מעל האלפבית הבינארי, מכיוון שכל מ״ט ניתנת לקידוד למחרוזת בינארית.

כפי שראינו בטענה הקודמת, יש יותר שפות ממחרוזות, ולכן יש יותר שפות מאשר השפות בRE.
}}

==הקבוצה <math>RE \setminus R</math> איננה ריקה==

בחלק קודם כבר ראינו [[תורת החישוביות/כריעות שפות#דוגמאות לשפות בRE|מספר דוגמאות לשפות בRE]]: השפה האוניברסלית, שפת האלכסון, ובעיית העצירה. כעת נראה כי שפות אלו הן ב<math>RE \setminus R</math>.

===אי-כריעות בעיית העצירה===

נניח, על דרך השלילה, שקיימת מ"ט כריעה, העונה על השאלה האם מ"ט M עוצרת על קלט x. נקרא למכונה זו H. כעת נבנה את המכונה 
<math>H'</math>
באופן הבא:
# בהנתן קידוד מ"ט M, המכונה קודם תריץ את <math>H(\langle M \rangle, \langle M \rangle)</math>, (נזכור שתמיד חלק זה עוצר, שכן הנחתנו בשלילה היא שהבעיה כריעה, וH מימוש שלה).
# אם התשובה חיובית, אז <math>H'</math> תכנס ללולאה אינסופית. אחרת, היא תעצור.

כעת נקבל מצב אבסורד לגבי הריצה <math>H' (\langle H' \rangle)</math>:
# אם היא עוצרת, אז בהכרח <math>H(\langle H' \rangle, \langle H' \rangle)</math> מחזירה תשובה שלילת (מפני שהיא השלב הראשון בריצת <math>H'</math> שכתוצאתו הוחלט לעצור). אבל לפי ההגדרה, משמעות תשובה שלילית זו היא ש<math>H' (\langle H' \rangle)</math> איננה עוצרת, ולכן יש סתירה.
# אם היא איננה עוצרת, אז בהכרח <math>H(\langle H' \rangle, \langle H' \rangle)</math> מחזירה תשובה חיובית (שוב, מפני שהיא השלב הראשון בריצת <math>H'</math> שכתוצאתו הוחלט להכנס ללולאה אינסופית). אבל לפי ההגדרה, משמעות תשובה חיובית זאת היא ש<math>H' (\langle H' \rangle)</math> עוצרת, ולכן שוב יש סתירה.

===אי-כריעות משלימת שפת האלכסון===

נתבונן בשפה המשלימה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|שפת האלכסון]], כלומר

<center><math>\overline{L_D} = \{ \langle M \rangle \;\mid\; \langle M \rangle \notin L(M) \}</math></center>.


{{טענה|תוכן=
<math>\overline{L_D} \notin R</math>
}}
{{הוכחה|1=
נניח בשלילה שאכן <math>\overline{L_D} \in R</math>, ולכן קיימת מ״ט <math>M_D</math> שמכריעה את <math>\overline{L_D}</math>. האם המכונה תקבל את המחרוזת <math>\langle M_D \rangle</math>?
# אם <math>\langle M_D \rangle \in \overline{L_D}</math> אזי מהגדרת השפה נובע כי <math>\langle M_D \rangle \notin L(M_D)</math>. במילים אחרות, אם מריצים את <math>M_D</math> על המחרוזת <math>\langle M_D \rangle</math>, המכונה לא תקבל את הקלט, ובפרט היא תדחה אותו (כי היא מכונה מכריעה). אבל, זו סתירה, כי הנחנו ש־<math>\langle M_D \rangle \in \overline{L_D}</math>, כלומר, הקלט בשפה ו־<math>M_D</math> צריכה לקבל אותו מכיוון שהיא מכריעה את השפה.
# לחלופין, אם מניחים כי המחרוזת אינה בשפה, <math>\langle M_D \rangle \notin \overline{L_D}</math>, אזי המכונה <math>M_D</math> צריכה לדחות את הקלט <math>\langle M_D \rangle</math>. מכאן ש־<math>M_D</math> אינה מקבלת את המחרוזת של עצמה, ולכן היא שייכת ל־<math>\overline{L_D}</math>, או באופן יותר מדוייק, הקידוד שלה נמצא בשפה זו, <math>\langle M_D \rangle \in \overline{L_D}</math> וזו סתירה להנחה.
}}

===אי-כריעות שפות נוספות דרך תכונות בסיסיות של רדוקציות ומשפטי רדוקציות===

בחלק זה נשתמש ב[[תורת החישוביות/כריעות שפות/רדוקציה#תכונות בסיסיות של רדוקציות|תכונות בסיסיות של רדוקציות]] ו[[תורת החישוביות/כריעות שפות/רדוקציה#תמשפטים|משפטי רדוקציה]] כדי להראות שמספר שפות אינן כריעות.


{{טענה|תוכן=השפה האלכסונית אינה כריעה, <math>L_D \notin R</math>.{{רווח קשיח|2}}}}
{{הוכחה|1=
נשים לב ש־R סגורה למשלים. לפיכך, מכיוון ש־<math>\overline{L_D} \notin R</math>, כך גם השפה המשלימה.
}}


{{טענה|תוכן=<math>L_U \notin R</math>}}
{{הוכחה|1=ראינו בפרק [[../רדוקציה/]] שמתקיים <math>L_D \le L_U</math> ולפי [[../רדוקציה#משפטים|משפט הרדוקציה – ההפכי]] נובעת המסקנה.}}

{{טענה|תוכן=<math>\text{HP} \notin R</math>}}
{{הוכחה|1=ראינו בפרק [[../רדוקציה/]] שמתקיים <math>L_U \le \text{HP}</math> ולפי [[../רדוקציה#ממשפטים|משפט הרדוקציה – ההפכי]] נובעת המסקנה.}}

{{תורת החישוביות|מוגבל}}
[[קטגוריה:תורת החישוביות]]