מכונת טיורינג רב־סרטית

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

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

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

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

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