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

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

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

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

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

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

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

רקע

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

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