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