משפט רייס – הגרסה המלאה

אי שם בראשית ימי הבלוג, כשדיברתי על תורת החישוביות הזכרתי גם את משפט רייס. באופן אינטואיטיבי, משפט רייס אומר שלא קיים אלגוריתם כללי שמסוגל, בהינתן קוד מחשב לחישוב של פונקציה כלשהי, לקבוע אם הפונקציה מקיימת תכונה "לא טריוויאלית" כלשהי, כשלא טריוויאלי פירושו "נכון לחלק מהפונקציות, אך לא לכולן". בשעתו נתתי הוכחה לגרסה הבסיסית והנפוצה של המשפט, אך מאז בגרתי והחכמתי ולמדתי על גרסה מלאה יותר ואני רוצה לנצל את הפוסט הזה כדי לתאר את המשפט עד הסוף.

ראשית, על אף שאפשר לנסח את המשפט עבור פונקציות כפי שעשיתי למעלה, הניסוח הסטנדרטי שלו הוא על שפות. שפה היא קבוצת מילים, כשמילה היא סדרת אותיות מתוך א"ב נתון כלשהו. בדרך כלל מניחים שהא"ב הוא הקבוצה $latex \left\{ 0,1\right\} $; זה לא ממש משנה משהו, מכיוון שפחות או יותר כל אובייקט מתמטי שבכלל אפשר להתעסק בו במחשב ניתן לתיאור כך – מספרים, גרפים, חבורות, קבצי מוזיקה, קידודים של תוכניות מחשב – בסופו של דבר כולם מיוצגים במחשב על ידי מילים שהאותיות שלהן הן 0 ו-1. שפה היא דרך לחלק את קבוצת כל המילים בעולם לשתיים – אלו שכן בשפה, ואלו שלא. למשל, אפשר לדבר על "שפת המספרים הראשוניים", או על "שפת הקבצים שמייצגים סרט וידאו שבאמצע שלו טום קרוז צץ ומתחיל לקפוץ על ספות", וכדומה.

נשתמש ב-$latex M$ כדי לסמן תוכנית מחשב (ולפורמליים שמביניכם – מכונת טיורינג; אך לא נזדקק להבדל הזה כאן) שמה שהיא עושה בחיים הוא לקבל קלט כלשהו בתחילת ריצתה, לעשות חישוב כלשהו (מבלי לקבל קלט נוסף מהמשתמש), ובסוף לפלוט "כן" או "לא". נסמן בתור $latex L\left(M\right)$ את קבוצת המילים ש-$latex M$ אומרת עליהן כן – "מקבלת" אותן; ל-$latex L\left(M\right)$ קוראים "השפה ש-$latex M$ מקבלת". לקבוצת השפות שקיימת $latex M$ שמקבלת אותן קוראים $latex \mbox{RE}$. שימו לב לאבחנה חשובה כאן – $latex M$ לא חייבת לעצור תמיד! אם היא לא עוצרת על קלט מסויים, ודאי שהיא אינה מקבלת אותו (כי לקבל פירושו לעצור ולהגיד "כן") ולכן הוא אינו בשפה שלה. אם $latex M$ דווקא כן עוצרת על כל קלט, אומרים שהיא מכריעה את $latex L\left(M\right)$, ולקבוצת השפות שקיימת מכונה שמכריעה אותן קוראים $latex \mbox{R}$. כפי שאתם ודאי מנחשים כבר (או יודעים כבר…), $latex \mbox{R}\ne\mbox{RE}$, כלומר היכולת של התוכנית לא לעצור על קלטים שעליהם התשובה שלילית מוסיפה לה כוח.

הדוגמה הקלאסית ביותר לשפה שנמצאת ב-$latex \mbox{RE}$ אבל לא ב-$latex \mbox{R}$, ולכן גם מראה שיש בעיות שלא ניתן לפתור באופן חד משמעי (כי "אני יושב ומחכה לראות אם החישוב אי פעם יסתיים…" זו לא תשובה מספקת למי שרוצה תשובת כן או לא חד משמעית) מכונה "בעיית העצירה". $latex \mbox{HP}$ בלועזית (מלשון Halting Problem) היא שפת כל תוכניות המחשב (זכרו – תוכנית מחשב היא בסך הכל סדרה ארוכה של אפסים ואחדים) שעוצרות מתישהו. שימו לב שאני לא מניח שהתוכנית מקבלת קלט – למעשה, אני מניח במוצהר שהתוכנית לא מקבלת קלט או מבצעת הגרלות כלשהן, כך שהריצה שלה היא תמיד אותו דבר. אפשר גם לדבר על גרסה שבה המכונה מקבלת קלט וכדומה (ולרוב זה מה שעושים) אבל איני צריך את זה כאן ואני די מעדיף את הגרסה הפשוטה הזו.

ראשית, שימו לב שבעיית העצירה ב-$latex \mbox{RE}$ די בבירור – בהינתן $latex M$, אני פשוט אריץ אותה ואחכה לראות אם החישוב נגמר. אם הוא נגמר, אגיד "כן". אם הוא לא נגמר – ובכן, בעסה לי, אחכה לנצח; אבל על פי ההגדרה של $latex \mbox{RE}$ זה לגיטימי.

מדוע בעיית העצירה אינה ב-$latex \mbox{R}$? כבר הקדשתי פוסט לעניין הזה, אך הנה הסבר חפוז: נניח שהיא כן, כלומר ניתן, בהינתן קוד של תוכנית מחשב, לקבוע אחרי חישוב שעוצר תמיד האם התוכנית הזו עוצרת או לא. אז אבנה תוכנית מחשב $latex M$ שעושה את הדבר הבא: בודקת, באמצעות התוכנית שפותרת את בעיית העצירה, האם $latex M$ עצמה עוצרת או לא. כלומר, $latex M$ מעבירה את הקוד של עצמה לאותה תוכנית שפותרת את בעיית העצירה. כעת, אם התשובה הייתה "כן, $latex M$ עוצרת" אז $latex M$ תכף ומייד תיכנס ללולאה אינסופית; ואם התשובה הייתה "לא, $latex M$ לא עוצרת" אז $latex M$ תכף ומייד תעצור.

למה הדבר דומה? לכך שנלך ברחוב ויבוא נביא ויטען "אני יודע איזו יד אתם הולכים להרים כעת!". אתם שואלים "כן? איזו יד?". הוא אומר "אה… שמאל?" ואתם מרימים מייד את ימין. כל עוד הדבר הבא שתעשו נקבע לפי התשובה של הנביא, אתם מסוגלים להפוך את הנביא לנביא שקר. לב ההוכחה כאן הוא בכך ש-$latex M$ מסוגלת לשאול את הנביא על עצמה; לא הוכחתי שהדבר אפשרי וזו אינה הוכחה טריוויאלית, אך כבר תיארתי את העניין בפוסט שזה בדיוק היה נושאו. בדרך כלל כשמדברים על בעיית העצירה מציגים גרסה קצת שונה שלה מבחינת הניסוח כדי לעקוף את הקושי הזה.

עכשיו אפשר להציג את משפט רייס. המשפט עוסק בתכונות של שפות. למשל, "אני מכילה את כל המספרים הזוגיים" היא תכונה של שפה, כמו גם "יש בי רק מספר סופי של מילים" או "לא קיימת תוכנית מחשב שמקבלת אותי". שפה טבעית היא דרך נהדרת לתאר תכונות של שפות, אבל איך אפשר לתאר תכונות באופן מתמטי כללי ככל הניתן? ובכן, כמו ששפה היא קבוצה של מילים שכולן מקיימות קריטריון מסויים, כך גם על תכונה אפשר לחשוב בתור קבוצה של שפות שכולן מקיימות קריטריון מסויים; ולמעשה, אין הכרח לציין את הקריטריון במפורש – אפשר פשוט להגדיר "תכונה של שפות" בתור קבוצה $latex S$ כלשהי של שפות.

השאלה שבה משפט רייס עוסק היא זו – האם אנחנו מסוגלים, בהינתן קוד של תוכנית מחשב $latex M$ כלשהי, לקבוע האם $latex L\left(M\right)\in S$?

כדי לפשט קצת את העניינים, מראש נגביל את $latex S$ להיות תת קבוצה של $latex \mbox{RE}$ – כלומר, במשחק שלנו כלל לא משתתפות שפות שאין מכונה שמקבלת אותן (ולכן הן ממילא לא רלוונטיות לשאלה אם $latex L\left(M\right)\in S$, שהרי הן אינן מהצורה $latex L\left(M\right)$ עבור אף $latex M$). השאלה שלנו, בניסוח הכי פורמלי שאפשר, היא זו – בהינתן $latex S\subseteq\mbox{RE}$, נגדיר שפה $latex L_{S}=\left\{ M|L\left(M\right)\in S\right\} $. האם $latex L_{S}\in\mbox{R}$? ואם לא, האם $latex L_{S}\in\mbox{RE}$, לכל הפחות? (כלומר, האם נוכל לפחות לעצור תמיד ולהגיד "כן" אם $latex L\left(M\right)\in S$, הגם שאם התשובה שלילית לא בהכרח נעצור?)

משפט רייס אומר ש-$latex L_{S}\in\mbox{R}$ רק במקרה שבו $latex S$ טריוויאלית – $latex S=\emptyset$ או $latex S=\mbox{RE}$ (התכונה לא מתקיימת לאף שפה, או שהיא מתקיימת לכל שפה ב-$latex \mbox{RE}$). במקרה הראשון, $latex L_{S}$ היא שפה ריקה ולכן תוכנית מחשב שמכריעה אותה פשוט אומרת מייד "לא"; במקרה השני תוכנית המחשב שמכריעה את $latex L_{S}$ פשוט אומרת מייד "כן". זה לא ממש מעניין, כמובן.

הבה ונוכיח בזריזות את משפט רייס (כבר עשיתי זאת בעבר, כאמור). ההוכחה היא באמצעות רדוקציה מ-$latex \mbox{HP}$ אל $latex L_{S}$. רדוקציה היא פשוט דרך להראות איך, אם $latex L_{S}$ ניתנת להכרעה, אפשר לנצל זאת גם כדי להכריע את $latex \mbox{HP}$ (ואת זה כבר אמרנו שאי אפשר לעשות). אם כן, נניח שיש לנו תוכנית מחשב שמכריעה את $latex L_{S}$. נניח לרגע כי השפה הריקה, $latex \emptyset$ אינה ב-$latex S$ (השפה הריקה היא פשוט השפה שאין בה כלל מילים; היא מתקבלת, למשל, על ידי תוכנית מחשבת שפולטת "לא" מייד לכל קלט). מכיוון ש-$latex S$ אינה טריוויאלית, יש בה לפחות שפה אחת – נאמר, $latex L\in S$. מכיוון ש-$latex S$ מכילה רק שפות ב-$latex \mbox{RE}$, אז יש תוכנית מחשב שמקבלת את $latex L$; נסמנה $latex M_{L}$.

כעת, מטרתנו היא לפתור את בעיית העצירה. אז נותנים לנו $latex M$ כלשהי ושואלים אותנו אם היא עוצרת או לא. מה שאנו עושים הוא לקחת את הקוד של $latex M$ ולהשתיל אותו בתוך תוכנית מחשב קצת יותר גדולה ומחוכמת, $latex U$. $latex U$ מקבלת קלט $latex w$ כלשהו, ואז עושה שני דברים:

  1. מריצה את $latex M$.
  2. מריצה את $latex M_{L}$ על הקלט $latex w$ ועונה כמוה.

מה הולך כאן? ובכן, אם $latex M$ עוצרת מתישהו, אז שלב 1 יסתיים מתישהו ושלב 2 יתחיל. לכן $latex U$ תתנהג על כל $latex w$ בדיוק כמו $latex M_{L}$, כלומר $latex L\left(U\right)=L\left(M_{L}\right)=L\in S$. במילים אחרות, אם $latex M$ עוצרת, השפה של $latex U$ היא בעלת התכונה $latex S$.

לעומת זאת, אם $latex M$ אינה עוצרת אף פעם גם $latex U$ לא תעצור אף פעם – היא נתקעת בשלב 1 ולא מגיעה כלל לשלב 2. לכן השפה של $latex U$ היא השפה הריקה, שאמרנו שאינה מקיימת את התכונה $latex S$. מכאן שאפשר להכריע אם $latex M$ עוצרת או לא על ידי כך שמכריעים אם השפה של $latex U$ היא בעלת התכונה או לא; סוף הסיפור.

מה קורה אם $latex S$ דווקא כן מכילה את השפה הריקה? כמעט אותו דבר. הפעם נבחר בתור $latex L$ שפה כלשהי שאינה ב-$latex S$ (קיימת כזו כי $latex S$ לא טריוויאלית), ונשים לב שכעת אם $latex M$ עוצרת, אז $latex U$ דווקא איננה בעלת התכונה, ואם $latex M$ אינה עוצרת אז $latex U$ היא כן בעלת התכונה; אבל עדיין – ברגע שהכרענו אם $latex U$ בעלת התכונה או לא, הסיפור נגמר.

זה מסיים את משפט רייס הבסיסי, וכעת אני רוצה לעבור אל מה שהוא מטרת הפוסט הזה – ההרחבה שלו. טיפלתי לחלוטין בשאלה מתי $latex L_{S}\in\mbox{R}$, אבל עדיין נותרה השאלה מתי $latex L_{S}\in\mbox{RE}$. כאן פתאום הסימטריה היפה של ההוכחה מתחילה להישבר. ראשית, אם $latex S$ אינה מכילה את השפה הריקה (המקרה הראשון בו טיפלנו) אז ההוכחה פשוט לא עובדת יותר אם כל מה שאנו מניחים הוא ש-$latex L_{S}\in\mbox{RE}$; אמנם, על ידי בדיקה אם $latex U$ בעלת התכונה עדיין נוכל להשתכנע ש-$latex M$ עוצרת, וזה מראה ש-$latex \mbox{HP}\in\mbox{RE}$, אבל את זה כבר ידענו – זה לא מוביל לסתירה כלשהי. אם $latex M$ לא עוצרת, אז $latex L\left(U\right)$ לא תהיה בעלת התכונה, ולכן אין שום דבר שמבטיח לנו שהתוכנית שמקבלת את $latex L_{S}$ תעצור בכלל על $latex U$.

לעומת זאת, אם $latex S$ כן מכילה את השפה הריקה, הסיפור שונה; במקרה הזה, אם $latex M$ לא עוצרת, אז $latex L\left(U\right)$ כן תהיה בעלת התכונה, ולכן התוכנית שמקבלת את $latex L_{S}$ כן תעצור מתישהו על $latex U$ ותגיד "כן". זה פותח לנו פתח להכרעה של $latex \mbox{HP}$: בהינתן $latex M$, ראשית נבנה ממנה את $latex U$ כמו קודם, ואז נעשה שני דברים במקביל – גם נבדוק אם $latex U\in L_{S}$, וגם נריץ את $latex M$ ונראה אם היא עוצרת. אפשר לבצע הרצות במקביל – המחשב שלכם עושה זאת כל הזמן (כמובן שהסיפור האמיתי מסובך יותר – לרוב מריצים תוכנית אחת לזמן מה, ואז מעבירים את הבקרה לתוכנית השניה, ואז חוזרים לראשונה, וכן הלאה). כעת מובטח לנו כי אחת משתי ההרצות תעצור מתישהו – אם $latex M$ עוצרת, אז ההרצה של $latex M$ עצמה תעצור; ואם היא לא עוצרת ולכן $latex L\left(U\right)$ בעלת התכונה, אז הבדיקה אם $latex U\in L_{S}$ תעצור מתישהו. במקרה הראשון (אם $latex M$ עצרה), נעצור גם אנחנו ונאמר "כן"; במקרה השני נעצור ונאמר "לא", והנה הכרענו את $latex \mbox{HP}$ – סתירה. לכן אם $latex \emptyset\in S$ הרי ש-$latex L_{S}\notin\mbox{RE}$. אבל זה כל מה שניתוח נאיבי של ההוכחה נתן לנו; אנחנו רוצים אפיון מוחלט, טענת "אם ורק אם". להבין בדיוק אילו תנאים על $latex S$ מבטיחים ש-$latex L_{S}\in\mbox{RE}$ ואילו תנאים מבטיחים כי $latex L_{S}\notin\mbox{RE}$.

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

בהינתן $latex S\subseteq\mbox{RE}$, השפה $latex L_{S}\in\mbox{RE}$ אם ורק אם $latex S$ מקיימת בו זמנית את שלוש התכונות הבאות:

  1. אם $latex L_{1}\in S$, $latex L_{2}\in\mbox{RE}$ ו-$latex L_{1}\subseteq L_{2}$ אז $latex L_{2}\in S$.
  2. אם $latex L_{1}\in S$ אז יש ל-$latex L_{1}$ תת-שפה סופית $latex L_{2}\subseteq L_{1}$ כך ש-$latex L_{2}\in S$.
  3. שפת כל השפות הסופיות שב-$latex S$ היא ב-$latex \mbox{RE}$.

התנאי השלישי דורש הסבר כלשהו. שפה סופית – שפה שמכילה רק מספר סופי של מילים – תמיד אפשר לקודד כמחרוזת סופית. אם המילים שלה הן $latex w_{1},w_{2},\dots,w_{n}$ אז המחרוזת $latex \left(w_{1},w_{2},\dots,w_{n}\right)$ (הסוגריים והפסיקים הם חלק מהמחרוזת – הם מקודדים על ידי תווי ASCII שמקודדים על ידי ספרות בינאריות) היא דרך לייצג את השפה בתור מילה סופית (עבור שפות אינסופיות אי אפשר לעשות תעלול דומה). התנאי השלישי, אם כן, אומר שבהינתן מחרוזת שמייצגת קבוצת מילים שכזו, אם היא מקיימת את התכונה $latex S$ אפשר לעצור ולומר זאת לאחר זמן סופי.

בואו נראה רגע איך המשפט הזה מתיישב עם מה שכבר ראינו. ראינו שאם $latex S$ לא טריוויאלית ו-$latex \emptyset\in S$ אז $latex L_{S}\notin\mbox{RE}$. מה המשפט החדש אומר? ובכן, $latex \emptyset$ היא בעלת התכונה שלכל $latex L$ מתקיים $latex \emptyset\subseteq L$, ולכן אם $latex S$ היא כזו ש-$latex L_{S}\in\mbox{RE}$ ובפרט היא מקיימת את תנאי 1, אז $latex L\in S$ לכל $latex L\in\mbox{RE}$, כלומר $latex S=\mbox{RE}$ ולכן זוהי תכונה טריוויאלית. כלומר, או ש-$latex S$ טריוויאלית, או ש-$latex L_{S}\notin\mbox{RE}$. אז אנחנו רואים בבירור שהמשפט שזה עתה הצגתי הוא הכללה של מה שכבר ראינו.

אז איך מוכיחים את המשפט? אני ממליץ לאלו מכם שיש להם נסיון כלשהו עם חישוביות לנסות ולהוכיח בעצמכם. זה מהמשפטים הללו שעיקר הקושי בהם הוא הגילוי של הקריטריון המתאים (איך בדיוק הגיעו לשלושת התנאים הללו? כנראה שהרבה ניסויים ובדיקה של מקרים פרטיים והתעמקות ומחשבה – כמו כל משפט מתמטי בערך), ומרגע שהניסוח הנכון קיים ההוכחה אינה כה נוראית.

הבה ונעבור להוכחה. ראשית נראה כי שלוש התכונות הללו הן הכרחיות, כלומר שאם משמיטים ולו אחת מהן, $latex L_{S}\notin\mbox{RE}$ בודאות.

ראשית נשמיט את תכונה 1, כלומר נניח שיש $latex L_{1},L_{2}$ כך ש-$latex L_{1}\subseteq L_{2}$ וגם $latex L_{1},L_{2}\in\mbox{RE}$ וגם $latex L_{1}\in S$ אבל $latex L_{2}\notin S$. כעת נכריע את $latex \mbox{HP}$ בדרך דומה למה שעוללנו קודם – בהינתן $latex M$, נבנה מכונה $latex U$ ששפתה תהיה $latex L_{1}$ אם $latex M$ אינה עוצרת, ו-$latex L_{2}$ אם היא כן עוצרת. אם $latex L_{S}\in\mbox{RE}$ זה אומר שנוכל לזהות מתי $latex M$ אינה עוצרת; וכאמור, לזהות מתי היא כן עוצרת אפשר לזהות פשוט על ידי הרצתה.

מה $latex U$ עושה, על קלט $latex w$? ובכן, היא מריצה את המכונה שמקבלת את $latex L_{1}$ על הקלט $latex w$, ובמקביל היא מריצה את $latex M$. אם בשלב כלשהו המכונה של $latex L_{1}$ עצרה וקיבלה את $latex w$, אז גם $latex U$ מקבלת את $latex w$; ואם בשלב כלשהו $latex M$ עצרה, אז $latex U$ מפסיקה את הרצת המכונה של $latex L_{1}$ על $latex w$ ותחת זאת מריצה את המכונה של $latex L_{2}$ על $latex w$ ועונה כמוה. מה הולך כאן?

ובכן, אם $latex M$ אינה עוצרת, אז $latex U$ תקבל את $latex w$ אם ורק אם $latex w\in L_{1}$; במילים אחרות, $latex L\left(U\right)=L_{1}$, כפי שרצינו; ואילו אם $latex M$ כן עוצרת, אז את $latex w$ אפשר לקבל בשתי צורות אפשריות – או שנקבל אותו כבר בהתחלה, אם נזהה שהוא ב-$latex L_{1}$; או שנקבל אותו בהמשך, אם נזהה שהוא ב-$latex L_{2}$. אלא ש-$latex L_{1}\subseteq L_{2}$, כך שהאפשרות שנקבל אותו בהתחלה לא משנה כלום – מובטח לנו ש-$latex L\left(U\right)=L_{2}$ במקרה זה, שבו $latex M$ עוצרת. כפי שרצינו.

יפה, אז התנאי הראשון הכרחי. ומה עם השני? גם כאן מניחים שהתנאי לא מתקיים ומוכיחים שאם עדיין $latex L_{S}\in\mbox{RE}$ אז אפשר להכריע את $latex \mbox{HP}$: נניח בשלילה שיש $latex L_{1}\in S$ שכל תת-שפה סופית שלה אינה ב-$latex S$; אז בהינתן $latex M$ נבנה $latex U$ כך שאם $latex M$ אינה עוצרת, $latex L\left(U\right)=L_{1}$, ואילו אם $latex M$ כן עוצרת, $latex L\left(U\right)$ היא שפה סופית כלשהי (ולכן לא ב-$latex S$). התעלול פשוט: $latex U$ על קלט $latex w$ תריץ את $latex M$ במשך $latex \left|w\right|$ צעדים – כלומר, מספר צעדים ששווה לאורך של $latex w$. אם $latex M$ עצרה במהלך הצעדים הללו, $latex U$ תעצור מייד ותגיד "לא"; אחרת, אחרי שהריצה את $latex M$ במשך $latex \left|w\right|$ צעדים, $latex U$ תתייאש ותריץ את התוכנית עבור $latex L_{1}$ על $latex w$ ותענה כמוה.

מה קרה כאן? אם $latex M$ עוצרת מתישהו, נניח אחרי 13 צעדים, אז $latex U$ תדחה כל מילה שאורכה גדול מ-13; ולכן השפה של $latex U$ סופית; ולכן היא אינה ב-$latex S$. אם לעומת זאת $latex M$ אינה עוצרת אף פעם אז $latex U$ תמיד תגיע לשלב שבו היא בודקת אם $latex w$ שייכת ל-$latex L_{1}$, ולכן שפתה תהיה בדיוק $latex L_{1}$. מכאן הדרך להכרעת $latex \mbox{HP}$ סלולה.

נותרנו עם התנאי השלישי. על פניו הוא נראה הסבוך מכולם, אבל במקרה שלו ההוכחה קלה עוד יותר ואפילו לא נזדקק להוכחה בדרך השלילה. אם $latex L_{S}\in\mbox{RE}$ זה אומר שבהינתן מכונה $latex M$, ניתן לבדוק אם $latex L\left(M\right)\in S$ ואם התשובה חיובית מובטח לנו שנעצור. אם כן, איך נבדוק, בהינתן שפה סופית $latex L$, ש-$latex L\in S$? פשוט מאוד: נבנה בעזרת הקידוד של $latex L$ מכונה $latex M$ כך ש-$latex L\left(M\right)=L$. מכונה כזו, בהינתן קלט, פשוט משווה אותו לרשימת המילים הסופית של $latex L$ ומקבלת אם הוא שם. כעת כל שנותר לעשות כדי לבדוק אם $latex L\in S$ הוא לבדוק אם $latex L\left(M\right)\in S$.

אם כן, הראנו כי אחד מהתנאים הללו בפני עצמו הוא הכרחי – אם הוא אינו מתקיים, $latex L_{S}\notin\mbox{RE}$. החלק המעניין כאן הוא האופן שבו השילוב של שלושתם – שלושה תנאים שנראים בלתי קשורים בעליל ממבט ראשון – מוכיח כי $latex L_{S}\in\mbox{RE}$. כמקודם, אני מאוד ממליץ לנסות ולחשוב על זה בעצמכם לפני שתקראו את ההוכחה.

בואו נבהיר לעצמנו מה צריך לעשות – אנחנו צריכים להראות איך, בהינתן תוכנית $latex M$, אפשר לבדוק אם $latex L\left(M\right)\in S$, כשהפריבילגיה שלנו היא שאם $latex L\left(M\right)\notin S$ אנחנו לא חייבים לעצור, אלא רק להימנע ממתן תשובה שגויה. אז השאלה שלנו היא – איך אנחנו יכולים להשתכנע ב-100 אחוזי ודאות ש-$latex L\left(M\right)\in S$?

השפות הסופיות ב-$latex S$ הן המפתח לפתרון. אם נגלה שפה סופית ב-$latex S$ כך ש-$latex M$ מקבלת את כל המילים שבה, אנחנו יכולים בודאות לסיים. מדוע? על פי תנאי מס' 1: אם הראינו כי $latex L\left(M\right)$ מכילה שפה סופית ב-$latex S$, תנאי 1 אומר שגם היא עצמה ב-$latex S$ ולכן ניתן בודאות לקבל.

אבל, תגידו, מי מבטיח לנו שבכלל קיימת שפה סופית ב-$latex S$ שאותה $latex L\left(M\right)$ מכילה? ובכן, תנאי 2, כמובן. שני התנאים מאפשרים לנו לנסח קריטריון אם-ורק-אם: $latex L\left(M\right)\in S$ אם ורק אם קיימת $latex L_{1}\subseteq L\left(M\right)$ סופית כך ש-$latex L_{1}\in S$.

האתגר שנותר הוא להסביר איך בודקים בפועל אם קיימת $latex L_{1}\in S$ כזו שמקיימת $latex L_{1}\subseteq L\left(M\right)$. את הבדיקה הזו עושים עם תעלול סטנדרטי נוסף בתורת החישוביות – הרצה מבוקרת.

הרצה מבוקרת היא דרך לרוץ על אינסוף קלטים "בבת אחת" או "במקביל", למרות ששתי המילים הללו אינן נכונות במיוחד. מה שאני רוצה לעשות הוא לבנות רשימה של כל המילים שעליהן $latex M$ עוצרת ומקבלת, אך סתם להריץ את $latex M$ על מילה כלשהי, לחכות עד שתסיים ואז לעבור למילה הבאה לא יעבוד, כי לא בטוח ש-$latex M$ תסיים בכלל. לכן התעלול הוא כזה: אני קובע סדר כלשהו על כל המילים הקיימות, $latex w_{1},w_{2},w_{3},\dots$ (שיטה אחת – להשוות קודם על פי האורך, ולאחר מכן על פי המספר שהמילה מייצגת). אני מריץ את $latex M$ זמן מה על $latex w_{1}$ ומפסיק. לאחר מכן אני מריץ אותה זמן מה על $latex w_{2}$, ומפסיק. אז אני חוזר להריץ אותה על $latex w_{1}$ תוך שאני ממשיך מאותה נקודה שבה הפסקתי קודם; ואז אני רץ על $latex w_{2}$. ואז על $latex w_{3}$. ואז שוב $latex w_{1}$, ושוב $latex w_{2}$, ושוב $latex w_{3}$, ואז $latex w_{4}$ – אתם מבינים את העיקרון. בכל "סיבוב" ריצה אני נותן הרצה לכל המילים שכבר התעסקתי איתן קודם, ומוסיף מילה חדשה למשחק. זה מבטיח שבסופו של דבר, כל מילה תזכה לכך שירוצו עליה זמן לא חסום, ולכן לכל מילה שאותה $latex M$ מקבל, בסוף אכן אגלה ש-$latex M$ מקבל אותה. זו נראית כמו שיטה בזבזנית למדי, אבל זה בדיוק האופן שבו דברים עובדים בתורת החישוביות – המקום שבו מתעניינים רק בשאלה אם משהו אפשרי ברמה הכי תיאורטית.

מה עכשיו? ובכן, בכל פעם שבה תתגלה מילה חדשה שאותה $latex M$ מקבלת, נבצע במקביל להרצה של $latex M$ על כל המילים האפשריות גם בדיקה נוספת – כל תת-קבוצה של המילים ש-$latex M$ קיבלה עד כה היא שפה סופית; פשוט נבדוק לכל שפה סופית כזו (שוב, על ידי הרצה מבוקרת) האם היא ב-$latex S$. אנחנו יכולים לעשות זאת, על פי כלל 3. אם מתישהו שפה סופית שכזו תתקבל, סיימנו – פשוט נעצור ונקבל. ואם אף פעם לא תתקבל שפה סופית שכזו? ובכן, החיים קשים ולא נעצור לעולם, אבל כבר אמרתי שאם אף שפה סופית שכזו לא מתקבלת, הרי שממילא $latex L\left(M\right)\notin S$ ולכן כל מה שאני מחוייב לו הוא לא לקבל, ובפרט מותר לי לא לעצור.

אם כן, זה מסיים את ההוכחה הכללית ביותר של משפט רייס. אם זו הפעם הראשונה שאתם נתקלים בדברים כאלו אני מניח שזה נראה לכם מטורלל משהו; אם כן, מצויין! זה בדיוק האופי של תורת החישוביות שאני רוצה להעביר. אחרי שמתרגלים קצת לתורת החישוביות רואים שההוכחה הזו היא מאוד פשוטה וטבעית (לא סתם הפצרתי בכם לנסות ולגלות אותה בעצמכם) ולטעמי – גם יפה בצורה בלתי רגילה.

13 תגובות בנושא “משפט רייס – הגרסה המלאה”

  1. חוסר הבנה שלי או פליטת קולמוס שלך ? (כנראה שחוסר הבנה שלי)

    השורה האחרונה בפסקה השלישית היא : " R!=RE, כלומר היכולת של התוכנית לא לעצור על קלטים שעליהם התשובה שלילית מוסיפה לה כוח".

    אממ, זה לא הפוך? כלומר, האם המילה "לא" מיותרת?נשמע מוזר שחוסר היכולת של מכונה לעצור מוסיף לה כח..

  2. שים לב – לא מדובר כאן על חוסר יכולת, אלא על "הרחבת הכללים". אנחנו דורשים מהתוכנית פחות – "מרשים" לה לא לעצור על קלטים מסויימים – ובעקבות כך היא מסוגלת לעשות יותר דברים.

  3. מאוד מאוד יפה בעיניי. לא הכרתי את הכרסה המורחבת הזו, וההוכחה קריאה ומובנת.
    תודה על פוסט טכני וכיפי גם יחד, בעיניי 🙂

    נקודה אחת שאולי קצת בעייתית – באיזה סדר כותבים את המילים בקידוד של שפה סופית כמילה?
    זה חשוב כאשר מריצים את התוכנה שמכריעה אם קידוד כזה מייצג שפה סופית שנמצאת ב-S.
    פרט טכני, שכמובן ניתן להתגבר עליו…

    האם מוכרות לך דוגמאות שבהן המשפט הזה שימושי? אולי תוצאות ידועות שעובדים הרבה בשביל לקבלן ללא המשפט? יש כאן די הרבה עבודה, אז זה מוכרח לחסוך עבודה במקומות אחרים.

    אפילו לגבי ההכרחיות של כל אחד משלושת התנאים במשפט, האם יש מקרים שבהם קל לראות שמתקיים אחד התנאים האלו וקשה להראות ישירות (עם רדוקציה פשוטה) שאין מכונה שמקבלת את השפה? ייתכן שלא כי המקרים הפרטיים של הרדוקציות האלו תמיד ייראו יותר פשוטים מההכללות? אבל מה לגבי התכונה השלישית?

    שוב תודה

  4. עניין הקידוד אכן דורש הבהרה כלשהי, אבל פחות או יותר כל הבהרה עובדת כאן – אפשר שהסדר יהיה הסדר הלקסיקוגרפי; אפשר שכל סדר ייחשב חוקי (וזה לדעתי הדבר ההגיוני לעשותו), ואפשר גם שהסדר יהיה שרירותי לחלוטין ואפילו לא נדע אותו מראש – זה לא חשוב, כי מכיוון שהשפה סופית אפשר פשוט לבדוק את כל הפרמוטציות האפשריות של מילים בתוכה.

    אין לי כרגע דוגמאות למקומות שבהם המשפט חוסך עבודה, אבל יכול להיות מעניין לעבור על תרגילים בקורס חישוביות סטנדרטי ולנסות להפעיל את המשפט בגרסה המלאה עליהן. אני מנחש שבחלק לא קטן מהמקרים זה יעזור. למשל, תרגיל מהקורס שאני מתרגל – "שפת המכונות שקיימת רדקוציה מבעיית העצירה לשפתן" נאכל בלי מלח על ידי המשפט המורחב (אין שפה סופית שמקיימת את התכונה, למרות שקיימת שפה אינסופית ב-RE שמקיימת אותה – HP עצמה).

  5. תודה רבה על ההסבר המעניין. אפשר לשאול של מי המשפט המורחב (אולי שלך?). הייתי רוצה לתת את הקרדיט המתאים.

  6. המשפט, כמו כל דבר אחר שהוצג בבלוג, אינו שלי. אני לא יודע מי הוכיח אותו לראשונה (רייס?); את הגרסה שאני מציג כאן ראיתי בספר של Hopcroft, Motwani, Ullman (מהדורה ראשונה, במהדורה השניה נראה לי שהם הורידו את זה).

  7. טוב, תודה רבה, ותודה שוב על הבלוג המעניין. העברתי (חלקית) את הדברים בדף זה לויקיספר (תורת החישוביות/כריעות שפות/משפט רייס). אתה מוזמן מאד להוסיף/להעיר וכו'.

  8. מה דעתך לגבי השפה הבאה, האם המשפט נכון גם לגביה?
    "L היא שפת קידודי המכונות שהשפה שלהן אינה כריעה."
    נראה לי שזו שפה שעומדת בקריטריונים והיא אינה ניתנת לזיהוי ע"פ ההרחבה. האם אני צודק?

  9. כשאתה בונה את המכונה U אתה מניח שיש לך את הקידוד של המכונה Lm. אם השפה L לא שייכת לS, וכל מה שאנחנו מניחים זה שLs שייכת לRE אז מהיכן יש לך את הקידוד? אתה מראה בדרך השלילה שאפשר להכריע את בעיית העצירה. אך למה לא לומר שהנחה שצריך לשלול היא שאפשר להשיג את הקידוד של Lm?

  10. אני לא בטוח לאיזה מקום בטקסט אתה מתייחס. תוכל להכווין אותי?

    בכל מקרה, "להשיג את הקידוד" זה ביטוי די לא מוגדר. רוב ההוכחות בחישוביות הן הוכחות קיום – אנחנו מראים שקיימת מכונה שכוללת בתוכנה קידוד כך-וכך והיא בעלת תכונות כך-וכך. זה לא אומר שאנחנו אישית יודעים איך לבנות את המכונה הזו ביט-אחר-ביט, רק שאנחנו יודעים להוכיח את קיומה.

  11. אשמח בבקשה להרחבה על המשמעות הפילוסופית של המשפט. מה בעצם ״מבחינה יומיומית״ אומר המשפט? מבחינה מטאפיזית וכד׳…
    למשל , האם זה אומר שמחשב לא יכול לתכנת בעצמו? כלומר שבניגוד למקצועות אחרים שמחשבים יכולים להחליף בני אדם , במקרה הזה התכנתים לא צריכים לדאוג?

  12. האם במשפט רייס, התכונה חייבת להיות מוכלת בתוך re?
    מה קורה לדוגמא כשהשפה היא המכונה M כך ששפת המכונה שייכת לco-re.

    האם ניתן לעשות רייס לשפה M כך ששפת המכונה מוכלת בHP? (מה התכונה?)

    תודה

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *