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

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

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

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

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

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

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

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

עכשיו אפשר להציג את משפט רייס. המשפט עוסק בתכונות של שפות. למשל, “אני מכילה את כל המספרים הזוגיים” היא תכונה של שפה, כמו גם “יש בי רק מספר סופי של מילים” או “לא קיימת תוכנית מחשב שמקבלת אותי”. שפה טבעית היא דרך נהדרת לתאר תכונות של שפות, אבל איך אפשר לתאר תכונות באופן מתמטי כללי ככל הניתן? ובכן, כמו ששפה היא קבוצה של מילים שכולן מקיימות קריטריון מסויים, כך גם על תכונה אפשר לחשוב בתור קבוצה של שפות שכולן מקיימות קריטריון מסויים; ולמעשה, אין הכרח לציין את הקריטריון במפורש - אפשר פשוט להגדיר “תכונה של שפות” בתור קבוצה \( S \) כלשהי של שפות.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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