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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
הדמיה של מכונת טיורינג

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

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

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

רקע[עריכת קוד מקור | עריכה]

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

תיאור - מרכיבים[עריכת קוד מקור | עריכה]

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

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

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

תיאור - אופן פעולה[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

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

שימושים של מכונות טיורינג[עריכת קוד מקור | עריכה]

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

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

ראו גם[עריכת קוד מקור | עריכה]

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]