אל R מ-RE: מניה רקורסיבית באינסוף צעדים

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

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

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

\( f_S(x)=\{\begin{matrix} 0 & x\notin S \\ 1 & x\in S \end{matrix} \)

ואנו רוצים אלגוריתם שמחשב את הפונקציה הזו.

על פניו, המעבר לבעיות הכרעה מגביל אותנו. בפועל, אין זה כך, במובן שלפיו בכל בעיה של “האם אפשר לחשב את הפונקציה הזו והזו” אפשר לדון גם במסגרת של בעיית הכרעה: אם יש לנו פונקציה f, אפשר להגדיר קבוצה S של זוגות של מספרים טבעיים באופן הבא: \( S=\{(x,y)|y=f(x)\} \). כל זוג של מספרים טבעיים אפשר לקודד בתור מספר טבעי באופן חד חד ערכי ועל (רק אתמול גיליתי שהפונקציה שעושה זאת היא קלה להפתיע: \( (x,y)\mapsto \frac{1}{2}((x+y)^2-x-3y+2) \) - נסו להוכיח זאת בעצמכם!) ולכן אין בשימוש בזוגות בעייה של ממש. כעת, אם אנחנו מסוגלים להכריע את הקבוצה S, אנחנו מסוגלים גם לחשב את f: בהינתן x, פשוט נעבור על כל המספרים הטבעיים y על פי הסדר, ונבדוק האם \( (x,y)\in S \). אם כן, הרי ש-\( f(x)=y \). אם לא, ממשיכים למספר הטבעי הבא, ובסופו של דבר נגיע ל-y הנכון.

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

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

קרוב לודאי שאצל חלקכם התעוררה כבר השאלה הבאה: אם יש קבוצות שאינן כריעות, איך בדיוק אפשר לתאר אותן? את מי מעניינת קבוצה S שאין דרך לתאר מה תוכנה?

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

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

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

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

מכאן שיש עניין תיאורטי גם בקבוצות שהן רק “כריעות למחצה” שכאלו, ואפילו יש להן שם. בעוד שלקבוצות כריעות “ממש” קוראים בצורה פורמלית “קבוצות רקורסיביות” - “Recursive sets” (מאותה הסיבה שלפונקציות שהזכרתי בתחילת הפוסט קוראים “רקורסיביות” - כאן המילה “רקורסיבית” היא פשוט שם אחר ל”ניתן לחישוב”), הרי שלקבוצות כריעות למחצה קוראים בצורה פורמלית “קבוצות ניתנות למניה רקורסיבית” - “Recursively enumerable sets”.

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

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

הדרך להתמודד עם הבעיה הזו היא “הרצה מבוקרת” של האלגוריתם שמבצע את הבדיקה, שמתנהלת כך: ראשית הוא מריץ את אלגוריתם הבדיקה על 1 במשך צעד בודד. אם סיים, מצויין, הוצא את 1 כפלט אם הוא שייך לקבוצה. אחרי זה הוא מריץ אותו על 1 במשך שני צעדים, ועל 2 במשך שני צעדים. אם סיים באחד מהמקרים, מצויין. אחרי זה הוא מריץ אותו על 1 במשך שלושה צעדים, על 2 במשך שלושה צעדים, על 3 במשך שלושה צעדים… וכן הלאה. כך מובטח שעל כל מספר הוא יריץ את הבדיקה למשך כל מספר של צעדים - ומכיוון שכל מספר ששיך לקבוצה יתגלה ככזה לאחר שהבדיקה תרוץ עליו במשך מספר סופי מסויים של צעדים, כל המספרים ששייכים לקבוצה יתגלו בשלב זה או אחר ויוצאו כפלט.

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

רק הערה אחרונה לסיום: מקובל לסמן את אוסף כל הקבוצות הרקורסיביות על ידי R, ואת כל הקבוצות הניתנות למניה רקורסיבית על ידי RE, וגם אני מתעתד לנהוג כך בהמשך.