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

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

רקע

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

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

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