המסע בעקבות הילברט וגדל
אלן מתיסון טיורינג (Alan Turing) נולד באנגליה ב-23 ביוני 1912. בהיותו בן 10 קיבל במתנה את ספרו של אדווין טֶני בְּרוּסטֶר (Brewster) 'פלאי הטבע שכל ילד חייב לדעת'. ברוסטר השתמש בספרו בדימויים מעולם המכונות לצורך תיאור פעולתם של המוח והגוף האנושי. אלן היה ילד פיקח וסקרן, שהתעניין במדע וחלם לערוך ניסויים מדעיים במו ידיו. ספרו של ברוסטר, שהסביר תופעות טבע שונות, פתח את עיניו של הילד אלן למשמעותה של חשיבה מדעית, והוליד בו את התשוקה לנסות ולפתור בעיות מדעיות.
בשנת 1926, בהיותו בן 14, נשלח אלן לבית־הספר שֶׁרבּוֹרן (Sherborne), שם נהגו מוריו לכנותו בשם "האלכימאי", מאחר והיה נוהג בזמנו הפנוי לבצע ניסויים שונים בכימיה ואהב להכין "נזידי מכשפות" מוזרים. בשרבורן התיידד טיורינג עם הנער כריסטופר מוֹרקוֹם (Christopher Morcom). בדומה לטיורינג התעניין גם מרקום יותר מכל בסוגיות מדעיות שונות. השניים נהגו לשוחח ביניהם על נושאים מתמטיים ופיזיקליים מגוונים, ביניהם מכניקה קוונטית ותורת היחסות, אבל הקשר לא היה אינטלקטואלי בלבד, ולפחות מצדו של טיורינג היה מדובר באהבת נעורים. מורקום היה קרוב למימוש חלומו כאשר הצליח להתקבל לטריניטי קולג' בקיימברידג'. אולם, עוד בטרם זכה להגשים את שאיפותיו, מת כריסטופר מורקום בשנת 1930 באופן פתאומי. מותו הכה בטיורינג הצעיר מהלומה קשה. טיורינג פנה לאמו של מורקום בבקשה שתעניק לו כמזכרת כמה מחפציו של בנה המנוח, אותם נצר לצידו בנאמנות. כעת הרגיש טיורינג צורך לא רק לממש את שאיפותיו שלו, אלא אף להגשים את חלומותיו של מורקום שנקטעו בדמי ימיו.
אלן טיורינג (איור: דנה אשכנזי)
בסתיו 1931 החל טיורינג את לימודי המתמטיקה בקינגס קולג' שבאוניברסיטת קיימברידג' (King's College, Cambridge), אותם סיים ב-1934. עבודת התזה שלו בקיימברידג' היתה בנושא: "על פונקצית השגיאה הגאוסינית" (On the Gaussian Error Function). בהסתמך על תזה זו קיבל טיורינג שנה לאחר מכן מעמד של עמית מחקר בקינגס קולג'. בעת שהותו בקיימברידג', מיזג טיורינג בין שני עולמות שהיו בעיניו מרתקים: עולם הלוגיקה המתמטית ועולם המכונות. מיזוג רעיוני זה הביא אותו בשנת 1936 לכתיבת המאמר: "על מספרים הניתנים לחישוב" (On Computable Numbers), שראה אור בינואר 1937. במאמרו זה ניסה טיורינג בדרכו המקורית להתמודד עם הבעיה העשירית של דויד הילברט (Hilbert). בשנת 1900 הציג הילברט 23 בעיות פתוחות במהלך כינוס עולמי בתחום המתמטיקה, שנערך בפריז. הבעיה העשירית שהציג הילברט זכתה בתולדות המתמטיקה לכינוי בעיית ההכרעה (Entscheidungsproblem).
דויד הילברט (איור: דנה אשכנזי)
בעיות אלו נתבו את כיווני המחקר במתמטיקה העיונית במאה ה-20. רוב אותן בעיות נפתרו מאז, חלקן הוכחו כבלתי פתירות (כלומר הוכחו כאקסיומות) ואילו שבע מהן עדיין פתוחות בימינו, הישג מדהים כשלעצמו. הילברט שאף לבסס באופן רשמי את המתמטיקה בכללותה על בסיס אקסיומות. באמצעות אותן אקסיומות האמין הילברט כי ניתן יהיה להראות את תקפותו של כל משפט מתמטי. אולם חלומו של הילברט בא אל קיצו בשנת 1931 כאשר הלוגיקן האוסטרי קורט גדל (Kurt Gödel) הוכיח במאמרו "טענות שאינן ברות הוכחה בפרינציפיה מתמטיקה ובמערכות דומות", כי הדבר אינו ניתן לביצוע, כלומר ישנן טענות שאינן ניתנות להוכחה או הפרכה. הוכחה זו של גדל מהווה נקודת ציון דרך בתחום הלוגיקה המתמטית, והיא זכתה לכינוי "משפט אי השלמות של גדל". משפטו זה של גדל נחשב לאחד המשפטים החשובים והמרכזיים במתמטיקה של המאה ה-20. בזכות אותה הוכחה, הוגדר גדל על ידי המגזין TIME כאחד מבין מאה המדענים החשובים ביותר במאה ה-20.
בעקבות הבעיה העשירית של הילברט, ו"משפט אי השלמות של גדל", העסיקה את מוחו הקודח של אלן טיורינג השאלה: האם קיים אלגוריתם המסוגל לאמת או להפריך כל טענה לוגית במערכת החזקה די הצורך כדי לייצג את המספרים הטבעיים? גדולתו של טיורינג היתה בכך שהוא היה זה שהגדיר לראשונה באופן מתמטי את המושג 'אלגוריתם'. הכוונה במושג זה היא לדרך מוגדרת ושיטתית שצעדיה משמשים לביצוע משימה מסוימת במספר מהלכים סופי. באופן יותר מפורט, האלגוריתם מסוגל לבצע פעולת חיבור, שבאמצעותה ניתן לבצע מניה של מספרים. בנוסף מסוגל האלגוריתם לשאול שאלות שהתשובה אליהן היא כן או לא, וכן מסוגל האלגוריתם לבצע לולאה, כלומר בהתאם לתשובה שהתקבלה, מסוגל האלגוריתם לחזור ולבצע שוב סדרת פעולות.
קורט גדל (איור: דנה אשכנזי)
במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה שפתרונה הוא "כן" או "לא". דוגמה לבעיית הכרעה היא השאלה: "האם מספר טבעי נתון הוא ראשוני?" מקרה פרטי של בעיית ההכרעה הנו בעיית העצירה, המהווה את אחד מעמודי התווך של תחום מדעי המחשב. בעיית העצירה עוסקת בשאלה האם, בעבור תוכנית מחשב ועבור קלט נתון, ניתן להכריע האם התוכנית תסיים בשלב כלשהו את פעולתה עבור אותו הקלט. למעשה, טיורינג הראה שבעיית העצירה אינה ניתנת להכרעה, כלומר אין אלגוריתם המסוגל להכריע עבור כל תוכנית מחשב האם היא ניתנת לעצירה. או, במילים אחרות, בעיית העצירה היא בעיה שאינה ניתנת להכרעה. מסקנה זאת הינה מפתיעה כשלעצמה, במיוחד כיום, כשרבים מאיתנו סבורים שמחשבים יכולים לבצע כל פעולה חישובית. למעשה, מה שהראה טיורינג במאמרו "על מספרים הניתנים לחישוב" הוא שקיימות בעיות שאינן ניתנות להכרעה ולחישוב. לשם כך הוא הגדיר "תהליך שאינו יכול להתבצע על־ידי מכונה אוטומטית". באמצעות מכונה תיאורטית הראה טיורינג שישנן בעיות שאינן ניתנות להכרעה. מכונה זו פותחה על־ידו כניסוי מחשבתי שמטרתו להבדיל בין בעיות מתמטיות הניתנות להכרעה לבין אילו שאינן ניתנות. לימים ניתן לה השם מכונת טיורינג (Turing Machine), והיא מהווה את הבסיס למחשב המודרני של ימינו.
מכונת טיורינג
מכונת טיורינג מורכבת מארבעה חלקים עיקריים: סרט (tape) המחולק לתאים (cells), ראש (head) שתפקידו לנוע על־פני הסרט ולבצע קריאה וכתיבה, טבלת הוראות (action table) שנותנת הוראות למכונה לאן לזוז ומה לכתוב בכל תא, ואוגר מצב (state register) בו נשמר מצבה העכשווי של המכונה. המכונה יודעת לעבור ממצב נתון אחד למשנהו. מצבה הראשוני של המכונה בתחילת פעולתה קרוי המצב ההתחלתי. הסרט מוגדר כאינסופי, כך שהוא ניתן להארכה ללא הגבלה הן לימין והן לשמאל. משמעות הדבר היא שלמכונה יש סרט בכל כמות הנדרשת. בכל תא יש סימן יחיד מתוך קבוצה סופית של סימנים אלפביתיים, לדוגמה, 0 או 1. אלפבית זה כולל סימן ריק, כלומר תאים שטרם נכתב בהם סימן. ראש המכונה מסוגל לקרוא ולכתוב את תוכנו של כל תא, ולזוז ימינה או שמאלה לאורך הסרט. הטבלה מורה לראש המכונה האם לזוז תא אחד ימינה או שמאלה, ולאיזה מצב חדש לעבור בהתאם לסימן שנקרא מהתא הנוכחי ולמצב הרשום באוגר המצב. בכל רגע של פעולת המכונה, הראש נמצא מול אחד התאים, ועל סמך הנתונים שעל הסרט, מחליטה המכונה על אופן פעולתה. המכונה יכולה לקרוא את הנתונים שמופיעים על הסרט ולכתוב על הסרט נתונים חדשים (בעזרת הראש), להזיז את הראש ימינה או שמאלה, ולשנות את מצב הבקרה הפנימי. כאשר אין בטבלה התייחסות לצירוף של המצב והסימן הנוכחיים, המכונה עוצרת. כל מרכיביה של מכונת טיורינג הם סופיים, מלבד הסרט שאינו מוגבל באורכו.
(איור: דנה אשכנזי וצבי לוטקר)
מכונת טיורינג מתחילה את החישוב ממצב התחלתי, כשעל הסרט כתוב מידע הקרוי קלט. מידע זה (הקלט) הוא סופי, והאלפבית של אותיותיו הוא חלקי לאלפבית של הסימנים שניתן לרשום על הסרט. חשוב להדגיש שהסמן ה"ריק" לא נחשב לחלק מהאלפבית של הקלט, והוא נועד כדי לציין היכן מסתיים הקלט. המכונה מסוגלת לשנות את מצבו של הסרט ואף עשויה לעצור בסופו של התהליך, כאשר תגיע לסימן הריק. האזור שבין תחילת הסרט למקום בו נעצר הראש קרוי הפלט של המכונה. חישוב באמצעות מכונת טיורינג, הקרוי גם תוכנית, משמעותו ביצוע סדרה של צעדי חישוב. לאחר שהמכונה מסיימת את החישוב היא עוצרת, ועל הסרט ניתן לקרוא את תוצאת החישוב (הפלט). לכן, ניתן לראות במכונת טיורינג מכונה שהופכת קלט לפלט. יתכן במכונה זו גם מצב שאינו ניתן להכרעה, בו עבור ערכים מסוימים הפונקציה המחושבת לא תהיה מוגדרת.
אופן ביצוע חישוב באמצעות מכונת טיורינג
לצורך המחשת אופן עבודתה של מכונת טיורינג, נביא דוגמה לפעולת חישוב פשוטה המתבצעת באמצעות מכונה זו. אולם, חשוב להדגיש כי ניתן בעזרת מכונת טיורינג לבצע גם פעולות מסובכות. בדוגמה הנוכחית המשימה היא להזיז על פני הסרט מילה, המורכבת מאפסים ואחדים. במשימה הנוכחית נזיז את המילה מקום אחד (תא אחד) שמאלה על פני הסרט, אולם באותו האופן ניתן היה לתת למכונה משימה להזיז את המילה תא אחד ימינה. באיור הבא ניתן לראות את הסרט במצבו ההתחלתי לפני ביצוע פעולה ההזזה (מצב א') ואת מצב הסרט לאחר ביצוע פעולת ההזזה (מצב ב').
(איור: דנה אשכנזי וצבי לוטקר)
האלגוריתם לפתרון המטלה: בתחילת המשימה (מצב התחלתי), הראש עומד מול הסימן הראשון במילה, כפי שניתן לראות במצב א' של האיור. מאחר והמילה נקראת משמאל לימין, הסימן הראשון שלה הוא הסימן השמאלי ביותר המוצג במצב א' שבאיור (1), והסימן האחרון שלה יהיה הסימן הימני ביותר המוצג במצב א' שבאיור (0). תחילה תקרא המכונה את הסימן הראשון במילה, הנמצא בצידה השמאלי. אז תזיז המכונה את הסימן השמאלי צעד אחד שמאלה. בשלב הבא יזוז ראש המכונה שני צעדים ימינה, ויקרא את הסימן הבא (השני) במילה. אחר־כך יוזז גם סימן זה תא אחד שמאלה. פעולה זאת תתבצע שוב (לולאת תזוזות), עד אשר בסיום התהליך יעמוד ראש המכונה מול תא ריק (כפי שניתן לראות במצב ב' שבאיור), המצביע על כך שהמכונה סיימה את הזזת כל המילה שמאלה על פני הסרט, ובכך תסתיים פעולת החישוב והמכונה תיעצר. באופן דומה, באמצעות אלגוריתם שונה במעט, יכולנו לבצע פעולה של הכפלת מספר ב-2.
טיורינג הראה שניתן לייצר מכונת טיורינג אוניברסלית (Universal Turing Machine) שתוכל לדמות את פעולתה של כל מכונת טיורינג אחרת. מכונת טיורינג היא, למעשה, מחשב פשוט המסוגל למבצע פעולה חישובית מסוימת. מכונת טיורינג האוניברסלית (UTM) תקבל כקלט I סדרת פעולות מתוך טבלת ההוראות של מכונת טיורינג מסוימת (TM) ואת הקלט של אותה מכונה. היא תקרא את הקלט I, תבצע באופן סידרתי את סדרת הפעולות של ה-TM ולבסוף תרשום על גבי הסרט שלה (של ה-UTM) את תוצאות פעולתה של ה-TM שקיבלה כקלט על גבי סרט הקלט של ה-UTM, זאת בהנחה שה-TM עוצרת. באופן זה ניתן לדמות באמצעות מכונה אחת את פעולתן של כל מכונות טיורינג. אלן טיורינג הוכיח שהמכונה האוניברסלית שלו יכולה לחשב כל בעיה שניתנת לחישוב על־ידי כל מכונה אחרת. בעיה שאינה ניתנת לחישוב בעזרת מכונת טיורינג האוניברסלית, לא יהיה ניתן לחשבה גם באמצעות כל מכונה אחרת. אחד מסוגי השאלות שניתן להציג בפני מכונת טיורינג הוא שאלות על אופן פעולתן של מכונות טיורינג אחרות. רבות מהשאלות הללו אינן ניתנות להכרעה, כלומר, אי אפשר לענות עליהן ב"כן" או "לא". כאמור, דוגמה לשאלה כזו היא בעיית העצירה, שטיורינג הראה שאינה ניתנת להכרעה.
בחלקו השני של המאמר נעסוק בתרומה שתרם טיורינג לפיצוח מכונת ה'אניגמה' הגרמנית, ובמחיר הכבד ששילם על סגנון חייו.
|
קישורים
|
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש