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

חישוב הוא מושג מוכר שרובנו מבינים באופן אינטואיטיבי. קח את הפונקציה f(x) = x + 3. מתי x הוא שלוש, f(3) = 3 + 3. שש. קַל. נראה ברור שהפונקציה הזו ניתנת לחישוב. אבל פונקציות מסוימות אינן כל כך פשוטות, וזה לא כל כך קל לקבוע אם ניתן לחשב אותן, כלומר אולי לעולם לא יתנו לנו תשובה סופית.

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

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

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

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

המכונה מתחילה במצב ההתחלתי, שנקרא לו q0. הוא קורא את התא השמאלי ביותר בקלטת שלנו ומוצא חלל ריק. הכללים אומרים, "במצב q0, אם הסמל הוא #, השאר אותו כפי שהוא ללא שינוי, הזז תא אחד ימינה, ושנו את מצב המכונה ל-q1." לאחר שלב זה, המכונה נמצאת במצב q1, והראש שלה קורא את הסמל השני, 0.

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

כאשר אנו מתייעצים שוב בטבלה, אנו מוצאים כלל חדש: "אם ניתקל ב-1, מעבר ל-q2, שהוא מצב 'דחייה'". המכונה עוצרת ועונה "לא" לשאלה המקורית, "האם '0001' אפס?"

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

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

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

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

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

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

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

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

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

המכונות המופשטות הללו הן אולי העדות הטובה ביותר לכך ששאלת שאלות בסיסיות יכולה להיות בין הדברים השימושיים ביותר שמדען יכול לעשות.