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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

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

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

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

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

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

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

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

[עריכה] מכונות טיורינג חלופיות

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

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

[עריכה] לקריאה נוספת

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