בשיעור הסיום נבנה מכונת טיורינג שפועלת אחרת על מספר זוגי ואי־זוגי, נוכיח שהפלט נכון ושהחישוב מסתיים. לאחר מכן נבדיל בין חישוב פונקציה, זיהוי שפה והכרעת שפה, ונכיר בקצרה את גבולות החישוב.
מטרות וידע קודם
נשתמש בסימון הסרט, השאריות והמעקב משיעור 13. נפרק אלגוריתם לשלבים שכל אחד מהם שומר אינווריאנט ברור. לפני ציור מכונה, נכתוב מה הקלט, איפה מתחיל הראש, מה נחשב פלט ועל איזה תחום נדרשת עצירה.
דוגמה פתורה 1 — מטלה 5 שאלה 4
הקלט הוא \(1^n\) עבור \(n>1\). הסרט בתחילה ⊢1ⁿΔ…, והראש על ה־1 הראשון. יש להחזיר בין שני סימני $ את:
מותר לשנות את הקלט ולהשאיר סימני עבודה מחוץ למקטע הפלט. אין דרישה לבדוק קלט שאינו בתחום. נשתמש ב־x לסימון אחדות שכבר עובדו.
אפשר לבחור מקום שונה לפלט בשני הענפים. באי־זוגי נשאיר את רוב הקלט במקומו; בזוגי נכתוב פלט חדש מימין לקלט. בשני המקרים התוצאה מזוהה באותה דרך: האחדות שבין שני סימני $.
קודם מזהים זוגיות
מתחילים ב־E. כל 1 מחליפה בין E ל־O בלי לשנות את הסרט. בתא הריק הראשון כותבים $ וחוזרים שמאלה בענף המתאים. הסימן $ הזה יהיה המפריד הימני בענף האי־זוגי, והמפריד השמאלי בענף הזוגי.
ענף אי־זוגי — חיסור אחד
חוזרים שמאלה עד ⊢, נעים ימינה ומחליפים את ה־1 הראשון ב־$. עוצרים. עבור 5 מתקבל ⊢$1111$Δ…, כך שהפלט 4. אין צורך למחוק את יתר הקלט או להזיזו.
ענף זוגי — אחד בפלט לכל זוג בקלט
חוזרים לתחילת הקלט, מסמנים את שני ה־1 הראשונים שטרם סומנו ב־x, מגיעים לימין מפריד $ ומוסיפים 1 לפלט. חוזרים לתחילה וחוזרים על התהליך. כשאין עוד 1 בקלט, מגיעים לסוף הפלט, כותבים את $ השני ועוצרים.
טבלת המעברים המלאה
המצב ההתחלתי E, ומצב העצירה halt. ברשימה 1,x כל סימן מייצג כלל נפרד שכותב את אותו סימן שנקרא. אין מעברים נוספים ואין מעברי אפסילון; כל שורה קוראת תא, כותבת ונעה L או R.
| מצב | קריאה | כתיבה | תנועה | יעד |
|---|---|---|---|---|
E |
1 |
1 |
R |
O |
O |
1 |
1 |
R |
E |
E |
Δ |
$ |
L |
back |
O |
Δ |
$ |
L |
oddBack |
oddBack |
1 |
1 |
L |
oddBack |
oddBack |
⊢ |
⊢ |
R |
oddFirst |
oddFirst |
1 |
$ |
R |
halt |
back |
1,x |
אותו סימן | L |
back |
back |
⊢ |
⊢ |
R |
pick |
pick |
x |
x |
R |
pick |
pick |
1 |
x |
R |
pair |
pair |
1 |
x |
R |
seek |
seek |
1,x |
אותו סימן | R |
seek |
seek |
$ |
$ |
R |
append |
append |
1 |
1 |
R |
append |
append |
Δ |
1 |
L |
return |
return |
1 |
1 |
L |
return |
return |
$ |
$ |
L |
back |
pick |
$ |
$ |
R |
close |
close |
1 |
1 |
R |
close |
close |
Δ |
$ |
R |
halt |
pair מצפה ל־1 שני; הוא תמיד קיים בקלט זוגי חוקי, כי מסמנים שניים בכל סיבוב. היעדר כלל ל־pair על $ אינו בעיה בתחום שהוגדר.
| נקודת בדיקה עבור \(n=6\) | מצב ומיקום הראש | סרט |
|---|---|---|
| אחרי בדיקת זוגיות וחזרה לתחילה | pick, על התא הראשון אחרי ⊢ |
⊢111111$ |
| אחרי סיבוב אחד וחזרה | pick, על התא הראשון אחרי ⊢ |
⊢xx1111$1 |
| אחרי שני סיבובים וחזרה | pick, על התא הראשון אחרי ⊢ |
⊢xxxx11$11 |
| אחרי שלושה סיבובים וחזרה | pick, על התא הראשון אחרי ⊢ |
⊢xxxxxx$111 |
| בסיום | halt, על הריק שאחרי המפריד הימני |
⊢xxxxxx$111$ |
זהו מעקב לפי סיבובים; למעקב צעד־צעד משתמשים בטבלה המלאה. אחרי \(j\) סיבובים יש בדיוק \(2j\) סימני x ו־\(j\) אחדות בפלט. מכאן שבסיום הפלט \(n/2\). כל סריקה עוברת על מקטע סופי ומתקדמת לכיוון גבול מוכר. מספר האחדות שטרם סומנו קטן בשתיים בכל סיבוב, ולכן הענף הזוגי מסתיים. בענף האי־זוגי שתי סריקות סופיות מספיקות.
לא די להשאיר אחת מכל שתי אחדות ולומר שזהו פלט אונרי: למשל 1x1x1x אינו המקטע הרציף 111 שנדרש בין המפרידים. כאן כתיבת הפלט באזור נפרד מבטיחה רציפות, והסימונים נשארים מחוץ לפלט.
דוגמה פתורה 2 — מזהה לעומת מכריעה
לשפה \(L=\{1^{2k}\mid k\ge0\}\) אפשר להשתמש במכונה שסורקת את הקלט תוך החלפת מצב זוגיות, ובסוף עוצרת בקבלה אם הזוגיות זוגית ובדחייה אחרת. זו מכריעה: כל קלט מקבל תשובה בזמן סופי. היא גם מזהה, כי כל מכריעה היא מקרה פרטי של מזהה.
כעת שנו את המכונה: על אורך זוגי היא עדיין עוצרת בקבלה, ועל אורך אי־זוגי היא נכנסת ללולאה שנעה ימינה לנצח על תאים ריקים. היא מזהה את אותה שפה, אך אינה מכריעה אותה. בכל צעד בלולאה עדיין נקרא תא סרט — אין כאן מעבר אפסילון.
| תפקיד | קלט בשפה | קלט מחוץ לשפה | מה מבקשים לבדוק? |
|---|---|---|---|
| מזהה שפה | עוצרת ומקבלת | דוחה או אינה עוצרת | קבלה בדיוק עבור חברי השפה |
| מכריעה שפה | עוצרת ומקבלת | עוצרת ודוחה | גם נכונות וגם עצירה לכל קלט |
| מחשבת פונקציה | השייכות לשפה אינה השאלה | תלוי בתחום הפונקציה | כתיבת הפלט הנדרש בתחום המוגדר |
המכונה בדוגמה 1 מחשבת פונקציה. השימוש במצב בשם halt אינו מסווג את הפלט כ”כן” או “לא”; יש לפרש את האחדות על הסרט.
השוואת מודלים וגבולות החישוב
| מודל | זיכרון נגיש | דוגמה ליכולת |
|---|---|---|
| DFA / NFA | מצב מתוך קבוצה סופית | רצפים, שאריות ותנאים רגולריים |
| PDA | מצב וראש מחסנית בלתי חסומה | התאמה כגון \(a^nb^n\) |
| מכונת טיורינג | סרט קריאה וכתיבה שאפשר לחזור לאורכו | השוואת כמה בלוקים וחישוב פלט |
אי־דטרמיניזם אינו מוסיף כוח זיהוי ל־DFA לעומת NFA, וגם לא למכונות טיורינג לעומת הגרסה הדטרמיניסטית. במחסנית, לעומת זאת, המודל הלא דטרמיניסטי הכללי חזק יותר מהדטרמיניסטי. מכונות טיורינג מרובות סרטים ניתנות לסימולציה על סרט אחד: הנוחות והיעילות עשויות להשתנות, אבל לא אילו פונקציות ניתנות לחישוב. בסימולציית אי־דטרמיניזם יש לחלק זמן בין הענפים; התעקשות על ענף יחיד עלולה להיתקע בו לנצח.
תזת צ׳רץ׳–טיורינג מזהה את רעיון החישוב האלגוריתמי האפקטיבי עם חישוב במכונת טיורינג. זו תזה על משמעות המושג אלגוריתם, ולא משפט שכל בעיה ניתנת לפתרון.
בעיית העצירה: אין אלגוריתם שמכריע לכל תוכנית וקלט האם התוכנית תעצור. אם היה בודק כללי כזה, אפשר היה לבנות תוכנית \(D\) שעל קוד של תוכנית \(P\) עושה ההפך מתחזית הבודק לגבי \(P\) על הקוד של עצמה: לולאה אם הבודק אומר “עוצרת”, ועצירה אם הוא אומר “לא עוצרת”. הפעלת \(D\) על הקוד של \(D\) יוצרת סתירה בשני המקרים. אין בכך איסור להוכיח עצירה של מכונה מסוימת, כפי שעשינו לעיל.
בסיום הקורס שאלו שלוש שאלות נפרדות: מהי השפה או הפונקציה? איזה מידע המודל צריך לזכור? ואיזו הוכחה מבטיחה שהבנייה נכונה? במכונת טיורינג הוסיפו גם: האם היא חייבת לעצור, ועל אילו קלטים?
תרגול
1. שני קצוות התחום
הריצו את דוגמה 1 על 2 ועל 3, וציינו את הסרט הסופי ואת הפלט המספרי.
רמז ופתרון
רמז: אלה המקרים הקטנים ביותר בכל ענף בתחום \(n>1\). פתרון: על 2, סיבוב זוגי אחד נותן ⊢xx$1$ והפלט 1. על 3, החלפת האחד הראשון נותנת ⊢$11$ והפלט 2. סימני ⊢ ו־x אינם בתוך מקטע הפלט.
2. איפה ההוכחה לעצירה?
תלמיד אומר “הרצתי על 2 עד 10, ולכן המכונה תמיד עוצרת”. השלימו את הטיעון החסר.
רמז ופתרון
רמז: חפשו כמות טבעית שיורדת בין סיבובים. פתרון: בענף הזוגי מספר האחדות שלא סומנו יורד בדיוק בשתיים; הוא אינו שלילי, ולכן יש \(n/2\) סיבובים. כל סריקה פנימית מגיעה לגבול במקטע סופי. בענף האי־זוגי יש רק סריקה ימינה וחזרה לגבול. בדיקות מגלות טעויות; האינווריאנט והכמות היורדת מוכיחים את הטענה לכל \(n>1\).
3. לזהות בעיה שאי אפשר להכריע
האם אפשר לזהות את שפת הזוגות “תוכנית וקלט שעליו היא עוצרת”, אף שאין לה מכריע כללי?
רמז ופתרון
רמז: אפשר להריץ את התוכנית המדוברת. פתרון: מדמים אותה על הקלט. אם היא עוצרת, מקבלים. אם אינה עוצרת, גם הסימולציה ממשיכה לנצח. זה מזהה את שפת העצירה אך אינו מכריע אותה. מכאן שהמושגים מזהה ומכריע אינם חלופיים.