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

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

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

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

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

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

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

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

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

מקורות:

[1] תורת הקוונטים אינה כריעה
[2] על בעיית העצירה

קריאה נוספת:

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