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

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

מכונת טיורינג (באנגלית: Turing machine) היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

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

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

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

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

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

רקע

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

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

תיאור המרכיבים

מכונת טיורינג מורכבת מהרכיבים הבאים:

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

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

תיאור אופן הפעולה

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

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

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

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

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

מכונת טיורינג שקוראת מספר בינארי וכותבת את המספר הנגדי לו בשיטת המשלים ל-2.

מכונות טיורינג חלופיות

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

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

שימושים של מכונות טיורינג

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

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

ראו גם

• תזת צ'רץ'-טיורינג
• מבחן טיורינג
• Brainfuck

לקריאה נוספת

• דוד הראל, אלגוריתמיקה – יסודות מדעי המחשב, האוניברסיטה הפתוחה, 1991

קישורים חיצוניים

• מכונת טיורינג, באתר MathWorld (באנגלית)
• מכונת טיורינג, באתר אנציקלופדיה בריטניקה (באנגלית)
• גדי אלכסנדרוביץ', המכונה המופלאה, באתר "לא מדויק", 23 בספטמבר 2007.
• שמואל וינוגרד, ‏מכונת טיורינג, מחשבות 35, יולי 1972, עמ' 13–17
• Alan Turing's 100th Birthday, דודל של גוגל לכבוד יום ההולדת ה-100 של אלן טיורינג המדמה את פעולתה של מכונת טיורינג.
• Turing Machine Visualization, פרויקט קוד פתוח לכתיבת קוד והרצתו על גבי מכונת טיורינג בצורה פורמלית, על ידי הגדרת טבלת מעברים, מכיל גם דוגמאות קוד.
• The Computer and Turing: Crash Course History of Science #36 – סרטון הסבר על ההיסטוריה של התפתחות המחשבים מתוך CrashCourse (באנגלית)
• Turing, A. M. COMPUTING MACHINERY AND INTELLIGENCE.