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

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

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

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

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

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

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

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

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

מקורות:

[1] הבסיס של המתמטיקה
[2] על מכונות טיורינג בבלוג "לא מדוייק"
[3] מבוא לאוטומטים ושפות רגולריות בבלוג "לא מדוייק"

לקריאה נוספת:

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