קידוד גדל

בלוגיקה מתמטית, מספר גדל (Gödel) הוא פונקציה המקצה לכל סמל ונוסחה בנויה-היטב של שפה פורמלית כל שהיא, מספר טבעי ייחודי, הנקרא מספר גדל שלה. המושג היה בשימוש על ידי קורט גדל להוכחת משפטי אי-השלמות שלו. (Gödel 1931)

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

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

הצגה מפושטת 

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

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

• המילה HELLO מיוצגת על ידי 72-69-76-76-79 באמצעות קוד ASCII עשרוני.
• הפסוק הלוגי x=y => y=x מיוצג על ידי 120-61-121-32-61-62-32-121-61-120 באמצעות ASCII עשרוני.

קידוד גדל

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

כדי לקודד נוסחה שלמה- רצף של סמלים, גדל השתמש במערכת הבאה. בהינתן רצף $(x_{1},x_{2},x_{3},...,x_{n})$ של מספרים חיוביים שלמים, קידוד גדל של הרצף הוא מכפלת n המספרים הראשוניים הראשונים, בחזקת הערכים המקבילים ברצף:

$\mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.\,$

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

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

ישנן דרכים מתוחכמות יותר (וקצרות יותר) לבנות מספרי גדל עבור רצפים.

דוגמה

בקידוד גדל הספציפי בו נייגל וניומן השתמשו, מספר גדל של הסמל "0" הוא 6 ומספר גדל של הסמל "=" הוא 5. לכן, במערכת שלהם, מספר של הנוסחה "0 = 0" הוא 2⁶ × 3⁵ × 5⁶ = 243,000,000.

אי-יחידיות הקידוד

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

לדוגמה, נניח שיש K סימנים בסיסיים, קידוד גדל חלופי יכול להיות בנוי על ידי מיפוי סט סמלים זה באופן הפיך (על ידי, למשל, פונקציה הפיכה h) לקבוצת הספרות של מערכת מספרית חד-ערכית בבסיס-K. נוסחה הכוללת מחרוזת של n סימנים $s_{1}s_{2}s_{3}\dots s_{n}$ תמופה למספר

$h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.$

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

למשל, עבור המספרים המתוארים בהוכחה של גדל, K=10000.

הכללות

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

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

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

לקריאה נוספת

• Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF), Monatsheft für Math. und Physik, 38: 173–198, אורכב מ-המקור (PDF) ב-2018-04-11, נבדק ב-2017-05-10.
• ההוכחה של גדל מאת ארנסט נייגל וג'יימס ר. ניומן (1959). ספר זה מספק מבוא טוב וסיכום של ההוכחה, ופרק גדול המוקדש למספרי גדל.
• גדל, אשר, באך, מאת דאגלס הופשטטר. ספר זה מגדיר ומשתמש במספור גדל חלופי.
• אני לולאה משונה מאת דאגלס הופשטטר. ספר חדש יותר של הופשטטר הכולל את ההיסטוריה של קידוד גדל.
• להמחיש את טיורינג – משתמש במספרי גדל כדי לקודד תוכניות.

קישורים חיצוניים

• קידוד צ'רץ'
• מספרי תיאור
• קידוד גדל על רצפים
• משפטי האי-שלמות של גדל
• משפט האי-כריעות של קולומגורוב