הבעיה העשירית של הילברט - נקמתן של הפונקציות הרקורסיביות והדיופנטיות

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

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

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

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

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

נניח שבאורח קסום כלשהו \( f \) הייתה דיופנטית והבעיה העשירית של הילברט הייתה פתירה, אז היינו פותרים את בעיית העצירה כך: בהינתן תוכנית מחשב שמקודדת על ידי ערכים \( a_{1},\dots,a_{a} \) ש-\( f \) מקבלת נציב את \( a_{1},\dots,a_{n} \) במשוואה הדיופנטית שמתאימה ל-\( f \), נפעיל את האלגוריתם שפותר את הבעיה העשירית של הילברט על המשוואה שהתקבלה, ואם אין לה פתרון נכריז שהתוכנית לא עוצרת, ואחרת נכריז שהתוכנית כן עוצרת. פשוט ביותר.

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

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

ראשית, כל משוואה דיופנטית היא כמובן ביטוי דיופנטי לגיטימי בשפה שלנו. משוואה דיופנטית היא משהו מהצורה \( p\left(x_{1},\dots,x_{n}\right)=0 \) כאשר \( x_{1},\dots,x_{n} \) הם משתנים כלשהם ו-\( p \) הוא פולינום. אפשר להכליל את זה קצת ולדבר על משוואות מהצורה \( p\left(x_{1},\dots,x_{n}\right)=q\left(x_{1},\dots,x_{n}\right) \) כאשר \( q \) גם הוא פולינום (גם 0 הוא פולינום חוקי מבחינתנו). המשוואה הדיופנטית שמייצגת את הביטוי \( p\left(x_{1},\dots,x_{n}\right)=q\left(x_{1},\dots,x_{n}\right) \) היא פשוט \( p\left(x_{1},\dots,x_{n}\right)-q\left(x_{1},\dots,x_{n}\right)=0 \) (כלומר, הפולינום \( p-q \) מייצג את הביטוי הזה).

כעת, אם \( P,Q \) הם שני ביטויים דיופנטיים שמיוצגים על ידי הפולינומים \( p,q \) בהתאמה, גם \( P\wedge Q \) הוא ביטוי דיופנטי שמיוצג על ידי הפולינום \( p^{2}+q^{2} \) (שמתאפס אם ורק אם \( p,q \) מתאפסים בו זמנית). עד כאן - הכל קל.

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

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

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

הפונקציות הרקורסיביות הבסיסיות היו הפונקציה הקבועה \( c\left(x\right)=1 \), פונקציית העוקב \( s\left(x\right)=x+1 \) ופונקציות ההטלה \( U_{i}^{n}\left(x_{1},\dots,x_{n}\right)=x_{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) \)

בכל המקרים הללו הביטוי הדיופנטי הוא מה שקראתי לו “ביטוי בסיסי” מהצורה \( p=q \) כאשר \( p,q \) הם שני פולינומים (ופולינומים פשוטים למדי במקרה שלנו). בניה קצת יותר מעניינת אפשר לתת אם זוכרים שהצלחנו להוכיח שהפונקציה \( h\left(n,k\right)=n^{k} \) היא דיופנטית. נניח שאנחנו רוצים להוכיח עכשיו שהפונקציה \( f\left(n,k,t\right)=n^{\left(k^{t}\right)} \) היא דיופנטית, את זה אפשר לעשות בקלי קלות:

\( y=n^{k^{t}}\iff\exists z\left(y=n^{z}\wedge z=k^{t}\right) \)

שימו לב: כאן \( n,k,t,y \) כולם פרמטרים שאנחנו הולכים להציב בפולינום שמתאר את הביטוי באגף ימין, ואחרי שנעשה את זה נישאר עם פולינום שהמשתנה החופשי היחיד שלו הוא \( z \), ו… רגע, האמנם?

בפולינום הזה יהיה כמובן את \( z \) בתור משתנה חופשי, אבל יהיו בו המון משתנים חופשיים אחרים ש”מוסתרים” כרגע מאיתנו. הביטוי \( y=n^{z} \) והביטוי \( z=k^{t} \) אומרים שניהם את אותו הדבר: עבדנו קשה בפוסטים הקודמים כדי לקבל פולינום מסובך מאוד שמתאר את הפונקציה הזו (אם תזכרו, בסופו של דבר קיבלנו מערכת של 11 משוואות). קחו את הפולינום שמתאים ל-\( z=k^{t} \) ואת הפולינום שמתאים ל-\( y=n^{z} \) (זה אותו פולינום אבל עם שמות שונים למשתנים שבתוכו) ועכשיו “תערבבו” אותם על פי הכלל של \( \wedge \) (דהיינו תעלו בריבוע ותחברו). התוצאה תיראה איום ונורא, אבל כל עוד אנחנו מסוגלים לתאר אותה בצורה הקומפטית \( \exists z\left(y=n^{z}\wedge z=k^{t}\right) \) ולדעת זה עובד, אנחנו מרוצים. וזה כמובן עובד, כי \( \exists z\left(y=n^{z}\wedge z=k^{t}\right) \) מקבל ערך אמת רק אם באמת \( y=n^{k^{t}} \).

בואו נמשיך לחסל את הפונקציות הרקורסיביות, ונעבור כעת לטפל בכללי הבניה שלהן - די לנו להראות שאם מפעילים את כללי הבניה על פונקציות דיופנטיות מקבלים פונקציה דיופנטית. הכלל הראשון היה הרכבה, ובו בנינו מתוך הפונקציות \( f,g_{1},\dots,g_{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) \). הביטוי הדיופנטי המתאים (שכבר הצגתי בעבר) הוא

\( 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) \)

שבנוי בדיוק על פי אותם עקרונות כמו \( \exists z\left(y=n^{z}\wedge z=k^{t}\right) \), רק באופן כללי. למעשה, אם תחשבו על כך לרגע, \( f\left(n,k,t\right)=n^{k^{t}} \) מתקבל מהפונקציה \( h\left(n,k\right)=n^{k} \) בעזרת הרכבה: \( f\left(n,k,t\right)=h\left(n,h\left(k,t\right)\right) \) (כלומר, מה שקראתי לו \( f \) בהגדרה הכללית של הרכבה הוא כאן \( h \), ואילו \( g_{1}\left(n,k,t\right)=n \) ו-\( g_{2}\left(n,k,t\right)=h\left(k,t\right) \)) כך שזה לא ממש מפתיע.

בואו נוסיף עוד כלל בניה של ביטויים דיופנטיים: הקשר “או”, \( \vee \). נניח שיש לנו את הביטויים \( P,Q \) עם פולינומים מתאימים \( p,q \) ואנחנו רוצים למצוא פולינום עבור \( P\vee Q \), כלומר כזה שמתאפס אם לפחות אחד משני הפולינומים מתאפס, מה נעשה? פשוט נכפול אותם: \( pq \).

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

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

כלל הבניה הבא בתור הוא מה שקראתי לו רקורסיה פרימיטיבית. בואו נזכיר אותו, כי הוא די קשה לעיכול. בניסוח לא פורמלי, אנחנו חושבים על קלט כלשהו למשתנים \( x_{1},\dots,x_{n} \) כאילו הוא מגדיר סדרה אינסופית \( a_{1},a_{2},a_{3},a_{4},\dots \) שמוגדרת באופן רקורסיבי. האיבר הראשון בסדרה מחושב בדרך כלשהי מתוך \( x_{1},\dots,x_{n} \); בואו נקרא לדרך הזו \( f \), כלומר \( a_{1}=f\left(x_{1},\dots,x_{n}\right) \). כעת, האיבר ה-\( k+1 \) בסדרה מחושב מתוך שלושה סוגי קלטים שונים: ראשית, הפרמטרים \( x_{1},\dots,x_{n} \) שאנו לא שוכחים מהם אף פעם; שנית, האיבר הקודם בסדרה, \( a_{k} \); שלישית, האינדקס של האיבר הקודם בסדרה, כלומר המספר הטבעי \( k \). נסמן ב-\( g \) את הפונקציה שמקבלת את שלושת הקלטים הללו: \( a_{k+1}=g\left(k,a_{k},x_{1},\dots,x_{n}\right) \). כעת אפשר להגדיר פונקציה \( h\left(x_{1},\dots,x_{n},k\right)=a_{k} \).

פורמלית זה הולך כך. אנו מגדירים \( h\left(x_{1},\dots,x_{n},1\right)=f\left(x_{1},\dots,x_{n}\right) \) ולכל \( k \) אנו מגדירים \( h\left(x_{1},\dots,x_{n},k+1\right)=g\left(k,h\left(x_{1},\dots,x_{n},k\right),x_{1},\dots,x_{n}\right) \). זה בדיוק מה שכתבתי למעלה, רק כתוב יותר פורמלי ויותר מבלבל.

התיאור שנתתי כאן מרמז על האופן שבו אפשר למדל את הבניה הזו עם ביטוי דיופנטי. הנה הנסיון הראשון לעשות את זה:

\( y=h\left(x_{1},\dots,x_{n},k\right)\iff\exists a_{1},a_{2},\dots,a_{k} \)

\( a_{1}=f\left(x_{1},\dots,x_{k}\right)\wedge \)

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

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

\( \dots \)

\( a_{k}=g\left(k-1,a_{k-1},x_{1},\dots,x_{n}\right)\wedge \)

\( y=a_{k} \)

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

לב הבעיה הוא בכך שכדי לתאר את הרקורסיה בשלב \( k \) אנחנו צריכים \( k \) משתנים, \( a_{1},\dots,a_{k} \), כלומר מספר משתנים שאינו קבוע אלא תלוי בפרמטר \( k \). אם הייתה איכשהו דרך לדחוף את כל המשתנים הללו לתוך משתנה יחיד…

וכאן הגיע הזמן להחזיר למשחק את הפונקציה שתיארתי בפוסט השלישי בסדרה: פונקציה דיופנטית \( S\left(i,u\right) \) שהיא בעלת התכונה הבאה: לכל סדרה סופית \( a_{1},\dots,a_{k} \) של מספרים טבעיים חיוביים, קיים \( u \) כך ש-\( S\left(i,u\right)=a_{i} \) לכל \( 1\le i\le k \). במילים אחרות, \( u \) מקודד את הסדרה \( a_{1},\dots,a_{k} \) במלואה. בעזרת הפונקציה הזו אפשר לכתוב מחדש את הביטוי שלעיל באופן הבא:

\( y=h\left(x_{1},\dots,x_{n},k\right)\iff\exists u \)

\( S\left(1,u\right)=f\left(x_{1},\dots,x_{k}\right)\wedge \)

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

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

\( \dots \)

\( S\left(k,u\right)=g\left(k-1,S\left(k-1,u\right),x_{1},\dots,x_{n}\right)\wedge \)

\( y=S\left(k,u\right) \)

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

\( y=h\left(x_{1},\dots,x_{n},k\right)\iff\exists u \)

\( S\left(1,u\right)=f\left(x_{1},\dots,x_{k}\right)\wedge \)

\( \forall i<k\left(S\left(i+1,u\right)=g\left(i,S\left(i,u\right),x_{1},\dots,x_{n}\right)\right)\wedge \)

\( y=S\left(k,u\right) \)

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

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

כזכור, מינימיזציה הולכת כך:

\( 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) \)

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

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

\( 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<y\left(f\left(x_{1},\dots,x_{n},t\right)\ne g\left(x_{1},\dots,x_{n},t\right)\right) \)

דבר אחד שעדיין צריך להסביר הוא איך לתאר את \( f\ne g \). זה פשוט קיצור של \( \left(f>g\right)\vee\left(f<g\right) \), ולכן כל מה שנותר לעשות הוא להשתכנע שאפשר להשתמש ב-\( < \), אבל זה אחד מהדברים הראשונים שהראיתי: כדי לתאר את \( x<y \) משתמשים במשוואה הדיופנטית \( x+z=y \). וזהו! סיימנו את ההוכחה של אי-כריעות הבעיה העשירית של הילברט!

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