הבעיה העשירית של הילברט - פונקציות דיופנטיות וחיות אחרות (רקורסיביות)

אנו ממשיכים בדרך שלנו אל ההוכחה שלא קיים אלגוריתם שפותר את הבעיה העשירית של הילברט. אני מניח שקראתם את פוסט המבוא ולכן קופץ ישר לעניינים הפעם. המושג המרכזי בפוסט הקודם היה קבוצה דיופנטית. זוהי קבוצה \( S=\left\{ \left(a_{1},\dots,a_{n}\right)\right\} \) של \( n \)-יות של מספרים טבעיים חיוביים, כך שקיים פולינום \( p\left(x_{1},\dots,x_{n},y_{1},\dots,y_{m}\right) \) בעל התכונה הבאה: למשוואה הדיופנטית \( q\left(y_{1},\dots,y_{m}\right)=0 \), עבור \( q\left(y_{1},\dots,y_{m}\right)=p\left(a_{1},\dots,a_{n},y_{1},\dots,y_{m}\right) \) יש פתרון בשלמים חיוביים אם ורק אם \( \left(a_{1},\dots,a_{n}\right)\in S \). אפשר גם לעשות ההפך - להתחיל מפולינום \( p\left(x_{1},\dots,x_{n},y_{1},\dots,y_{m}\right) \) ולסמן קבוצה \( S_{p} \) שכוללת את כל ה-\( n \)-יות שכאשר מציבים אותם במקום ה-\( x \)-ים, מקבלים משוואה דיופנטית עם פתרון בשלמים חיוביים.

אם לא הבנתם כלום ממה שכתבתי כרגע, נסו לקרוא שוב את המבוא.

בפוסט הקודם ראינו שאפשר להגדיר יחסים מוכרים באופן הזה, למשל את יחס החלוקה (שהוא קבוצת הזוגות \( \left(a,b\right) \) כך ש-\( a|b \), כלומר \( a \) מחלק את \( b \), כלומר קיים \( c \) שלם כך ש-\( b=ac \)). בואו נראה לצורך החימום עוד דוגמה - היחס “קטן-שווה”, הידוע גם כ-\( a\le b \). נגדיר אותו באופן הבא:

\( x\le y\iff\exists z\left(x+z-1=y\right) \)

רגע, מה? מה הולך כאן? מה אלו הסימונים הללו? אני עובר לשיטה שבה מרטין דיוויס משתמש במאמר שלו כי היא אלגנטית וקצרה יותר. כאן הפולינום שלי הוא \( p\left(x,y,z\right)=x+z-1-y \), והמשתנים שבהם צריך להציב ערכים הם \( x,y \) ואז לראות אם למשוואה הדיופנטית שנותרה לנו, שיש בה רק את המשתנה \( z \), יש פתרון. די ברור בסימון של דיוויס מי המשתנים ששייכים לקבוצה הראשונה (אלו שבאגף שמאל של החצים) ומי המשתנים שבקבוצה השניה (אלו שיש סימן \( \exists \) - “קיים” לפניהם) והיכן הפולינום עצמו (מה שבסוגריים, עד כדי העברת אגפים אם יש צורך). אז אני מקווה שאנחנו מיודדים עם הסימון הזה כעת וגם מבינים למה הפולינום שלעיל אכן מגדיר את \( x\le y \).

עכשיו, תרגיל - מה השתנה כאן?

\( x<y\iff\exists z\left(x+z=y\right) \)

ולמה?

עכשיו בואו נעבור למשהו קצת יותר מתוחכם. ראינו כבר שיש פולינום \( p_{1} \) שמגדיר את הקבוצה \( S_{p_{1}}=\left\{ \left(a,b\right)\ |\ a|b\right\} \). ראינו גם שיש פולינום \( p_{2} \) שמגדיר את הקבוצה \( S_{p_{2}}=\left\{ \left(a,b\right)\ |\ a\le b\right\} \). האם יש פולינום שמגדיר את הקבוצה \( S=\left\{ \left(a,b\right)\ |\ a\le b\wedge a|b\right\} \) (\( \wedge \) הוא הסימן של “וגם”; ו-\( \vee \) הוא הסימן של “או”), כלומר הקבוצה \( S_{p_{1}}\cap S_{p_{2}} \)? התשובה חיובית: הפולינום \( p_{1}^{2}+p_{2}^{2} \). למה? כי אחרי הצבת ערכים בו, נשאר עם משוואה דיופנטית שהדרך היחידה שלה להתאפס היא שגם \( p_{1}^{2} \) יתאפס וגם \( p_{2}^{2} \) יתאפס (כי אם אחד מהם לא מתאפס, אז אחרי העלאה בריבוע הוא חיובי ולכן הסכום יהיה גדול מאפס). את העניין הזה אפשר כמובן להכליל לחיתוך על מספר סופי כלשהו של נחתכים. המסקנה: מחלקת הקבוצות הדיופנטיות סגורה לחיתוכים סופיים. ומה עם איחודים סופיים? גם אותם אפשר לקבל. הקבוצה \( S_{p_{1}}\cup S_{p_{2}} \) מוגדרת על ידי הפולינום \( p_{1}p_{2} \) - הוכיחו זאת לעצמכם.

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

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

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

נתחיל מהכיוון הקל. נניח שיש לנו קבוצה \( S \) שמוגדרת על ידי \( p\left(y_{1},\dots,y_{n}\right) \) בדרך ה”חדשה” שתיארתי - \( S \) היא קבוצת הערכים החיוביים ש-\( p \) יכול להחזיר. אנחנו רוצים למצוא פולינום \( q \) כך ש-\( S=S_{q} \), כאשר \( S_{q} \) מוגדרת בשיטה הישנה (ערכים שאחרי שמציבים אותם ב-\( q \) מקבלים משוואה דיופנטית פתירה). מה נגדיר? פשוט מאוד: \( q\left(x,y_{1},\dots,y_{n}\right)=x-p\left(y_{1},\dots,y_{n}\right) \). ברור שכאשר \( a\in S \) אז \( q\left(a,y_{1},\dots,y_{m}\right) \), שמגדיר את המשוואה \( a=p\left(y_{1},\dots,y_{n}\right) \) יהיה פתיר; וכמובן שאם \( a=p\left(y_{1},\dots,y_{n}\right) \) פתירה אז \( a\in S \), ממש על פי הגדרה.

האתגר הוא הכיוון השני. נניח ש-\( S_{q} \) מוגדרת על ידי \( q \) בצורה ה”ישנה”; איך נמצא פולינום \( p \) שמגדיר אותה בצורה ה”חדשה”? ובכן, נניח ש-\( a\in S \). אז \( q\left(a,y_{1},\dots,y_{m}\right) \) פתיר - אפשר לקבל ממנו אפס. לכן \( p\left(y_{1},\dots,y_{m}\right)=a-q\left(a,y_{1},\dots,y_{m}\right) \) הולך להחזיר \( a \) כאשר מציבים בו בדיוק את הערכים של ה-\( y \)-ים שמאפסים את \( q\left(a,y_{1},\dots,y_{m}\right) \). אבל זה לא מספיק טוב, כי עבור ערכים שונים של ה-\( y \)-ים \( q \) לא בהכרח יתאפס ואז \( a-q\left(a,y_{1},\dots,y_{m}\right) \) יהיה מספר לא קשור. רק מה, צריך לזכור שמותר ל-\( p \) להחזיר מספרים לא קשורים, בתנאי שהם שליליים (או אפס) אז בואו נוודא שנחזיר מספר שלילי, פשוט על ידי כוח גס: \( p\left(y_{1},\dots,y_{m}\right)=a\left(1-q^{2}\left(a,y_{1},\dots,y_{m}\right)\right) \). הבהירו לעצמכם למה הפולינום הזה עושה את העבודה.

אבל רגע, עוד לא סיימנו! הפולינום שלנו עושה את העבודה עבור ערך ספציפי של \( a \), ואנחנו רוצים שהוא יעבוד לכל \( a \). זו לא בעיה, כמובן: הפולינום ה”נכון” הוא \( p\left(x,y_{1},\dots,y_{m}\right)=x\left(1-q^{2}\left(x,y_{1},\dots,y_{m}\right)\right) \), ועכשיו באמת סיימנו את הוכחת המשפט.

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

הבנו קבוצות דיופנטיות? יפה. אז בואו נעבור לסוג מיוחד של קבוצה - פונקציה. פונקציה היא יחס - קבוצה של איברים מהצורה \( \left(x_{1},\dots,x_{n},y\right) \) - עם התכונה המיוחדת שלכל \( x_{1},\dots,x_{n} \) קיים \( y \) כך ש-\( \left(x_{1},\dots,x_{n},y\right) \) שייך לקבוצה, ואותו \( y \) הוא יחיד. חשבו על \( \left(x_{1},\dots,x_{n}\right) \) בתור “קלט” ועל \( y \) בתור “פלט” של הפונקציה. לרוב מסמנים פונקציה ב-\( f \), ואז במקום לומר ש-\( \left(x_{1},\dots,x_{n},y\right) \) שייך לפונקציה, כותבים \( f\left(x_{1},\dots,x_{n}\right)=y \). רובכם בוודאי יודעים את זה (אבל זכרו שלא כל מי שמכיר פונקציות גם מכיר את הגדרתן הפורמלית, התורת-קבוצתית).

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

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

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

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

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

הפונקציות הרקורסיביות הבסיסיות הן:

1. הפונקציה הקבועה \( c\left(x\right)=1 \).
2. פונקציית העוקב \( s\left(x\right)=x+1 \)
3. פונקצית ההטלה, \( U_{i}^{n}\left(x_{1},\dots,x_{n}\right)=x_{i} \) (המוגדרת לכל \( n,i \)).

טוב, עבור פונקציות הבסיס הללו לא קשה לראות שהן דיופנטיות. הפונקציה הראשונה מוגדרת על ידי:

\( y=c\left(x\right)\iff\left(y=1\right) \)

השניה מוגדרת על ידי:

\( y=s\left(x\right)\iff\left(y=x+1\right) \)

והשלישית מוגדרת על ידי:

\( y=U_{i}^{n}\left(x_{1},\dots,x_{n}\right)\iff\left(y=x_{i}\right) \)

טוב, זה היה מטופש למדי. איפה האתגר? בהמשך.

הפעולה הראשונה שממנה בונים פונקציות רקורסיביות חדשות מתוך הקיימות היא הרכבה. היא מוגדרת כך: אם \( g_{1},\dots,g_{m} \) הן פונקציות רקורסיביות על המשתנים \( x_{1},\dots,x_{n} \) ואילו \( f \) היא פונקציה רקורסיבית על \( m \) משתנים, אז הפונקציה \( h\left(x_{1},\dots,x_{n}\right)=f\left(g_{1}\left(x_{1},\dots,x_{n}\right),\dots,g_{m}\left(x_{1},\dots,x_{n}\right)\right) \) גם היא רקורסיבית. מה שאנחנו רוצים להראות הוא שאותו הדבר קורה עם פונקציות דיופנטיות, כלומר שאם \( g_{1},\dots,g_{m},f \) כולן דיופנטיות, כך גם \( h \).

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

\( y=h\left(x_{1},\dots,x_{n}\right)\iff\exists t_{1},\dots,t_{m}\left(y=f\left(t_{1},\dots,t_{m}\right)\wedge t_{1}=g_{1}\left(x_{1},\dots,x_{n}\right)\wedge\dots\wedge t_{m}=g_{m}\left(x_{1},\dots,x_{n}\right)\right) \)

מה בעצם עשינו כאן? אגף ימין מגדיר פולינום גדול, שמקבל בתור משתנים את \( x_{1},\dots,x_{n} \) וגם את המשתנים \( t_{1},\dots,t_{m} \). עכשיו הוא לוקח את הפולינום שמגדיר את \( f \) (כשהמשתנים בו מתאימים ל-\( t_{1},\dots,t_{m} \) ו-\( y \)), את הפולינום שמגדיר את \( g_{1} \) (כשהמשתנים בו מתאימים ל-\( x_{1},\dots,x_{n} \) ו-\( t_{1} \)), את הפולינום שמגדיר את \( g_{2} \) (כבר הבנתם…?) וכן הלאה עד \( g_{m} \), ואז מחבר את הריבועים של כולם (זו מהות ה-\( \wedge \) שעושים על כולם).

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

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

רקורסיה פרימיטיבית מוגדרת כך: בהינתן פונקציה רקורסיבית \( f \) על \( n \) משתנים (“תנאי ההתחלה”), ופונקציה רקורסיבית \( g \) על \( n+2 \) משתנים (“צעד הרקורסיה”), אנחנו מגדירים פונקציה חדשה, \( h \), על \( n+1 \) משתנים (שעליהם כדאי לחשוב כך: \( n \) המשתנים הראשונים הם “פרמטרים” קבועים ואילו המשתנה האחרון הוא מה שעליו מוגדרת הרקורסיה), באופן הבא:

\( h\left(x_{1},\dots,x_{n},1\right)=f\left(x_{1},\dots,x_{n}\right) \)

\( h\left(x_{1},\dots,x_{n},t+1\right)=g\left(t,h\left(x_{1},\dots,x_{n},t\right),x_{1},\dots,x_{n}\right) \)

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

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

\( y=h\left(x_{1},\dots,x_{n},z\right)\iff\exists t_{1},t_{2},\dots,t_{z}(t_{1}=f\left(x_{1},\dots,x_{n}\right)\wedge \)

\( \wedge t_{2}=g\left(1,t_{1},x_{1},\dots,x_{n}\right)\wedge t_{3}=g\left(2,t_{2},x_{1},\dots,x_{n}\right)\wedge\dots \)

\( \wedge t_{z}=g\left(z-1,t_{z-1},x_{1},\dots,x_{n}\right)\wedge y=t_{z}) \)

מה הולך כאן? אנחנו אומרים ש-\( y=h\left(x_{1},\dots,x_{n},z\right) \) רק אם קיימת סדרה \( t_{1},\dots,t_{z} \) שהאיבר הראשון בה הוא \( f\left(x_{1},\dots,x_{n}\right) \) - הערך ההתחלתי הנכון, בהינתן הפרמטרים - וכל איבר בה נובע מקודמו על ידי \( g \), וכמו כן האיבר האחרון הוא \( y \). מבחינה רעיונית הכל נכון; הבעיה היא סינטקטית - הפסוק שכתבתי כאן לא מתאים ל”שפה” שהצגתי עד כה, מה שאומר שעל פניו לא ברור אם אפשר איכשהו לתרגם אותו חזרה לפולינום שמגדיר פונקציה דיופנטית. בעיה מהותית אחת היא שאורך הפסוק אינו קבוע! הוא תלוי ב-\( z \), כי ככל ש-\( z \) יותר גדול, יש יותר משתנים \( t_{1},\dots,t_{z} \). אם עבור ערכים שונים של \( z \) יש פסוקים שונים, זה אומר שגם יהיו פולינומים שונים, אבל אנחנו צריכים פולינום יחיד שמטפל בכל \( z \). לכן הבניה הזו לא מוצלחת ונזדקק לפיתוח של כלי טכני חדש - פונקציה דיופנטית שמסוגלת לקודד סדרות שרירותיות - על מנת להציע בניה טובה יותר, וגם זה לא יספיק לנו. אבל על כך נדבר בהמשך.

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

אם כן, פונקציות שניתנות ליצירה באמצעות כללי היצירה הנוכחיים מתוך פונקציות הבסיס נקראות פונקציות פרימיטיביות רקורסיביות, וקיימות פונקציות ניתנות לחישוב שאינן פרימיטיביות רקורסיביות. הכלל שפותר את הבעיה הזו הוא כלל שמאפשר לבצע “חיפוש בלתי חסום”: אם נתונות פונקציות רקורסיביות \( f,g \) על \( n+1 \) משתנים, אז מוגדרת באמצעותן פונקציה רקורסיבית \( h \) על \( n \) משתנים באופן הבא:

\( h\left(x_{1},\dots,x_{n}\right)=\min_{y}\left(f\left(x_{1},\dots,x_{n},y\right)=g\left(x_{1},\dots,x_{n},y\right)\right) \)

כמקודם, חשבו על \( x_{1},\dots,x_{n} \) בתור “פרמטרים”. אחרי שקבענו אותם, אנחנו יכולים לחפש את ה-\( y \) המינימלי שעבורו \( f \) תהיה שווה ל-\( g \), וזה הערך ש-\( h \) תחזיר על אותם פרמטרים. אלא שכאן מייד צצה השאלה הפשוטה - מה קורה אם בכלל לא קיים \( y \) כזה? התשובה היא שבמקרה זה \( h \) תהיה לא מוגדרת על הקלט. מרגע שהכנסו את הכלל החדש הזה, שנקרא כלל המינימיזציה לתמונה, גרמנו לכך שקבוצת הפונקציות הרקורסיביות תכלול גם פונקציות חלקיות, כאלו שלא מוגדרות לכל הקלטים (ולמעשה, אפילו הפונקציה שאינה מוגדרת לאף קלט היא רקורסיבית; פשוט קחו את \( f \) להיות הפונקציה שמחזירה תמיד 1 ואת \( g \) להיות הפונקציה שמחזירה תמיד 2). מה שמעניין כאן הוא שפונקציית אקרמן שהזכרתי לעיל כן מוגדרת לכל קלט, כלומר כלל המינימיזציה הכרחי כדי שנוכל “לתפוס” את כל הפונקציות הניתנות לחישוב שמוגדרות לכל קלט; זה לא שהוספנו אותו רק כדי להיות מסוגלים לטפל בפונקציות חלקיות.

טוב, אז הבנו בערך מה זה הכלל הזה; איך אפשר להראות שאם \( f,g \) דיופנטיות, כך גם \( h \)?

שוב, מבחינה רעיונית הפסוק שמגדיר את התכונה הזו אינו מסובך:

\( y=h\left(x_{1},\dots,x_{n}\right)\iff f\left(x_{1},\dots,x_{n},y\right)=g\left(x_{1},\dots,x_{n},y\right)\wedge \)

\( \wedge\forall t\left(t<y\to f\left(x_{1},\dots,x_{n},y\right)\ne g\left(x_{1},\dots,x_{n},y\right)\right) \)

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

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