מה דחף לוגיקנים לחקור מהו חישוב יעיל?

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

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

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

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

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

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

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

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