מכונת טיורינג – המדריך המלא

הגדרה פורמלית

מכונת טיורינג היא שביעייה M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject), כאשר:

• Q – קבוצה סופית של מצבים.
• Σ – אלפבית הקלט (לא כולל את הסימן ⊔ של "תא ריק").
• Γ – אלפבית הסרט (Σ ⊆ Γ), כולל את הסימן ⊔.
• δ : Q × Γ → Q × Γ × {L, R} – פונקציית המעברים. בהינתן מצב והסימן שתחת הראש, היא מחזירה מצב חדש, סימן לכתיבה וכיוון תזוזה.
• q₀ ∈ Q – מצב התחלתי.
• q_accept, q_reject ∈ Q – מצב מקבל ומצב דוחה (שונים זה מזה). ברגע שמגיעים לאחד מהם הריצה נעצרת.

מבנה המכונה

מכונת טיורינג מורכבת משלושה רכיבים פיזיים מופשטים:

1. סרט אינסופי – חלוק לתאים, כל תא מכיל סימן מתוך Γ. בהתחלה הסרט מכיל את הקלט, ובכל שאר התאים יש ⊔.
2. ראש קריאה/כתיבה – מצביע על תא אחד, יודע לקרוא ולכתוב, ולנוע צעד אחד שמאלה (L) או ימינה (R).
3. בקרת המכונה – נמצאת באחד מהמצבים ב־Q. בכל צעד היא מחליטה מה לעשות לפי δ.

איך המכונה רצה?

בכל צעד המכונה מבצעת את הפעולה הבאה:

1. קוראת את הסימן שתחת הראש.
2. מפעילה את δ על (מצב נוכחי, סימן שנקרא) ומקבלת (מצב חדש, סימן לכתוב, כיוון תזוזה).
3. כותבת את הסימן החדש על הסרט (במקום שתחת הראש).
4. זזה תא אחד לכיוון שהוחזר (L או R).
5. עוברת למצב החדש וחוזרת לשלב 1 – אלא אם המצב החדש הוא q_accept או q_reject.

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

דוגמה: מכונה שמחליפה כל 0 ב־1

בונים מכונה שעוברת על הקלט משמאל לימין, ומחליפה כל 0 ל־1. עוצרת ב־q_accept ברגע שהיא נתקלת בתא ריק.

Q = {q₀, q_accept}, Σ = {0, 1}, Γ = {0, 1, ⊔}.

על קלט 010 הריצה היא: q₀-0 → כתוב 1, ימינה ; q₀-1 → כתוב 1, ימינה ; q₀-0 → כתוב 1, ימינה ; q₀-⊔ → q_accept. הסרט בסוף הריצה: 111.

שפה מקובלת ושפה כריעה

• שפה מתקבלת ע״י מכונת טיורינג (recursively enumerable) – קיימת מכונה שמקבלת כל מילה בשפה. על מילים שלא בשפה היא עשויה לא לעצור.
• שפה כריעה (decidable) – קיימת מכונה שעוצרת על כל קלט, ומקבלת בדיוק את מילות השפה.
• כל שפה כריעה היא מתקבלת – אך לא להפך. שפת העצירה היא הדוגמה הקלאסית לשפה מתקבלת שאינה כריעה.

חשיבות – תזת צ׳רץ׳–טיורינג

תזת צ׳רץ׳–טיורינג טוענת שכל פונקציה "ניתנת לחישוב" באופן אינטואיטיבי – ניתן לחשב במכונת טיורינג. כלומר, מכונת טיורינג מגדירה את הגבול העליון של מה שמחשב יכול לחשב, ולא משנה כמה הוא חזק. לכן כל שפה לא כריעה (כמו שפת העצירה) אינה ניתנת לחישוב בכל מחשב, לא רק במכונת טיורינג.