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

לא ניתן לעשות שימוש מסחרי בחומר זה ללא רשות בכתב מן המחברים או מערכת כתב העת

אלן טיורינג – חייו ותרומתו למדעי המחשב

עריכה: שרה לב

 

סקירה כללית

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

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

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

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

 

תחילת הדרך

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

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

 On computable numbers, with an application to the Entscheidungsproblem.

 

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

 

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

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

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

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

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

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

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

טיורינג המשיך בלימודיו באוניברסיטת פרינסטון, והשלים את תואר הדוקטורט שלו בשנת 1938, בהנחייתו של המתימטיקאי האמריקאי צ'רץ' (Alonzo Church). אז חזר לאנגליה, וקבל מילגה מחודשת לקמברידג'.

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

 

תקופת מלחמת העולם השניה

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

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

 

לאחר מלחמת העולם השנייה

לאחר המלחמה, הועתקו תחומי העניין של טיורינג מהתיאוריה לבנייה מעשית של מחשבים ממשיים.

בשנת 1945 הצטרף לצוות של המעבדה הפיזיקלית הלאומית בלונדון, כדי להוביל את העיצוב, הבנייה והשימוש של המחשב הדיגיטלי האלקטרוני רחב המימדים, שנקרא Automatic Computing Engine (ACE).

בשנת 1948 מונה להיות המשנה למנהל של מעבדת המחשבים באוניברסיטת מנצ'סטר, שבה נבנה באותה עת המחשב בעל קיבולת הזכרון הגדולה בעולם באותם הימים: Manchester Automatic Digital Machine- MADAM.

 

טיורינג ואינטליגנציה מלאכותית

בשנת 1950, כתב טיורינג את המאמר הנבואי שלו שהתפרסם בכתב העת 'Mind'. שם המאמר היה "מכונות חישוב ואינטליגנציה", או במקור ”Computing Machinary and Intelligence”.

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

 

יחד עם חברו הטוב, דיויד צ'מפרנון (David Champernowne), תכנן טיורינג את תכנית המחשב הראשונה שמשחקת שחמט, בשם  ‘TuroChamp’. צ'מפרנון נודע בזכות עבודתו על הלחנה ממוחשבת של מוסיקה, והיה שחקן שח להוט כמו טיורינג עצמו.

 

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

 

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

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

 

מכונת טיורינג

לפי האפיונים של טיורינג, המכונה מורכבת משלושה מרכיבים בסיסיים: סרט (tape) המורכב מסדרה אינסופית של תאים (cells), ראש קורא/כותב (head), ובקרה סופית (finite control).

 

 

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

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

 

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

 

דוגמה לחישוב במכונת טיורינג

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

למשל, אם במצב ההתחלתי הסרט נראה כך  

...

 

 

1

0

1

 

 

...

 

 

אז לאחר החישוב, הוא יראה כך

...

 

1

0

1

 

 

 

...

 

האלגוריתם לפתרון המשימה

נניח שבתחילת התהליך, הראש עומד מול התו הראשון במילה.

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

וביתר פירוט:

·        קרא את התו הראשון במילה וסמן את המקום שקראת בעזרת הסימן $.

·        זוז מקום אחד שמאלה וכתוב שם את התו שקראת.

·        זוז ימינה (חזרנו למקום הקודם שהטיפול בו הסתיים) ומחק את הסימן המיוחד $ (במקומו ישאר מקום ריק, או רווח).

·        זוז ימינה (לתו הבא במילה).

·        חזור על התהליך כולו עד שהמילה תסתיים (כלומר, המילה כולה הועברה מקום אחד שמאלה).

 

כדי לתאר את החישוב בצורה יותר פורמלית נעזר בסימונים הבאים:

 (qi , תו) = (qj , סימן, סוג תזוזה)

 

"תו" הוא התו שהראש קורא כעת על הסרט (מעין תו קלט).

"סימן" הוא התו שאותו יכתוב הראש בתא שמולו הוא נמצא כעת (מעין תו פלט).

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

qj הוא מצב פנימי של המכונה. למשל, q0  הוא המצב ההתחלתי.

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

 

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

 

הפתרון הפורמלי:

 (q0, 0) =  (q10 , $, L)

 (q0, 1) =  (q11 , $, L)

 (q0, $) =  (q0, B, R)

 (q10 , B) =  (q0, 0, R)

 (q11 , B) =  (q0, 1, R)

 (q0, B) עצור  :

 

 

הסבר הפתרון הפורמלי:

·        המצב ההתחלתי הוא q0 (הראש עומד מול התו הראשון של המילה וקורא 0 או 1).

·        במצב q0, אם הראש קורא את התו 0, אזי המכונה תעבור למצב החדש q10 (מצב 1 שעברנו אליו בגלל שבקלט הופיע 0), הראש יכתוב $ במקום הנוכחי (כדי לסמן את המשבצת הנמצאת ב"טיפול"), והראש יזוז מקום אחד שמאלה L.

·        במצב q0, אם הראש קורא את התו 1, אזי המכונה תעבור למצב החדש q11 (מצב 1 שעברנו אליו בגלל שבקלט הופיע 1), הראש יכתוב $ במקום הנוכחי (כדי לסמן את המשבצת הנמצאת ב"טיפול"), והראש יזוז מקום אחד שמאלה L.

·        במצב ההתחלתי q0, אם הראש קורא את הסימן $, המכונה תישאר באותו מצב q0, הראש ימחק את הסימן המיוחד (יפנה את המקום לתו הבא במילה), ובמקומו "יכתוב רווח" B, והראש זז מקום אחד ימינה R.

·        במצב q10, אם הראש קורא B (כלומר מקום ריק), המכונה חוזרת למצב ההתחלתי q0, הראש כותב 0 במקום הפנוי וזז מקום אחד ימינה R .

·        במצב q11, אם הראש קורא B (כלומר מקום ריק), המכונה חוזרת למצב ההתחלתי q0, הראש כותב 1 במקום הפנוי וזז מקום אחד ימינה R.

·        במצב q0, אם הראש רואה מקום ריק B (הסתיימו התווים של המילה), אזי המכונה עוצרת.

 

מקורות

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

  2.  Encyclopedia Britannica, Turing Alan M., Chicago, 1988, pp. 56.

  3.  Hofstadter D. R., (1980). Godel, Escher, Bach: An eternal golden braid, Vintage Books, New York, pp. 594-595.

  4.  Kurzweil Raymond, The Age of  Intellegent Machines (1990), MIT Press.

  5.  Andrew Hodge’s biography (1983): Alan Turing: the Enigma.

  6.  Turing Sara (1959), Alan M. Turing, Cambridge, UK, W. Heffer & Sons.

מקורות נוספים על טיורינג ועבודתו ברשת האינטרנט:

http://www.turing.org.uk/turing/

http://cogsci.ucsd.edu/~asaygin/tt/ttest.html

http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Turing.html

http://plato.stanford.edu/entries/turing-machine/

http://plato.stanford.edu/entries/church-turing/

http://ei.cs.vt.edu/~history/Turing.html

http://www.turingarchive.org/

http://www.time.com/time/time100/scientist/profile/turing.html

 


אתר הבטים

תוכן לפי נושאים

תוכן לפי גליונות

תוכן דצמבר 95

חזרה לתחילת העמוד