מודלים ומשאבי חישוב

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

מטרות

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

אינטואיציה

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

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

$t_M(n)$ הוא מספר הצעדים המרבי של $M$ על קלט באורך $n$. המקום $s_M(n)$ הוא מספר תאי סרט העבודה המרבי שבהם ביקרה המכונה; לפי המקובל, סרט הקלט לקריאה בלבד אינו נספר. קונפיגורציה כוללת מצב, תוכן סרטים ומיקומי ראשים.

מכונת טיורינג דטרמיניסטית חד־סרטית היא

כאשר $Q$ סופית, $\Sigma\subseteq\Gamma$, הסימן הריק $\sqcup\in\Gamma$, ו

בקלט $x$, הסרט מכיל תחילה את $x$ ואחריו ריקים, הראש מעל הסימן הראשון והמצב $q_0$. צעד קורא וכותב סימן אחד, מחליף מצב ומזיז את הראש תא אחד. דטרמיניזם אומר שהמצב והסימן הנוכחיים קובעים לכל היותר מעבר אחד.

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

קונפיגורציות וחישובים

כתיב $u q av$ מתאר תוכן $uav$, מצב $q$ וראש הסורק את $a$. מסמנים $C\vdash_M C'$ למעבר יחיד ו-$\vdash_M^*$ לאפס מעברים או יותר. חישוב הוא

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

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

קידודים ומכונה אוניברסלית

מכונה היא עצם סופי ולכן אפשר לקודד את מצביה, סימניה וטבלת המעברים בביטים. קידוד $\langle x,y\rangle$ חייב להיות חד־חד־ערכי וניתן לפענוח יעיל; שרשור ללא מפריד עלול להיות עמום. מחרוזות שאינן קידוד תקין יכולות להידחות או להתפרש כמכונה טריוויאלית, לפי מוסכמה קבועה.

מכונה אוניברסלית $U$ מקיימת

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

התקורה תלויה בקידוד. כאשר $M$ קבוע, קבועים רשאים להיות תלויים בתיאורה; כאשר $\langle M\rangle$ הוא חלק מהקלט, גם אורכו נספר. אוניברסליות אינה מבטיחה זמן זהה אלא סימולציה בעלת תקורה מבוקרת.

דוגמה. מכונת זוגיות סורקת ימינה ומחליפה בין מצבי ״זוגי״ ו״אי־זוגי״ בכל קריאת $1$. בריק הראשון היא מקבלת בדיוק אם מספר האחדות זוגי. היא רצה $n+1$ צעדים. מכונה אוניברסלית על תיאורה ועל $x$ תחזיר אותה תשובה, בדרך כלל לאט יותר.

משפט עמידות. אפשר לדמות מכונת טיורינג דטרמיניסטית מרובת סרטים בזמן $t(n)$ באמצעות מכונה חד־סרטית בזמן $O(t(n)^2)$, תחת המוסכמות הרגילות.

מהלך ההוכחה

מקודדים את הסרטים הווירטואליים על סרט יחיד, עם מפרידים וסימוני ראשים. כל צעד מדומה סורק את האזור שבשימוש ומעדכן אותו. לאחר $t(n)$ צעדים נגישים רק $O(t(n))$ תאים, ולכן כל צעד עולה $O(t(n))$ והעלות הכוללת ריבועית.

בפירוט: הסימולטור מציב $k$ מסילות ומסמן ראש בכל אחת. סריקה אחת אוספת את $k$ הסימנים למצב הסופי; טבלת המעברים הקבועה קובעת כתיבות ותזוזות; סריקה נוספת מעדכנת את המסילות. אם ראש וירטואלי מגיע לתא חדש, מרחיבים את הייצוג. אחרי $t(n)$ צעדים כל ראש הגיע לכל היותר ל-$t(n)+1$ תאים, ולכן אורך הייצוג הוא $O(t(n))$ עבור $k$ קבוע. יש $t(n)$ צעדים מדומים וכל אחד עולה $O(t(n))$.

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

מדידת זמן ומקום

למכריע,

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

מכונה הרצה $t(n)$ צעדים יכולה להגיע רק ל-$O(t(n))$ תאים, ולכן זמן חוסם מקום. הכיוון ההפוך אינו נכון: אפשר להשתמש שוב באותם תאים זמן רב. עם זאת, למכונה קבועה המשתמשת ב-$s(n)\ge\log n$ מקום יש רק $2^{O(s(n))}$ קונפיגורציות; מכריע לא יכול לחזור על אחת מהן.

דוגמה פתורה

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

כל סיבוב מבצע לכל היותר שתי סריקות באורך $O(n)$, ויש לכל היותר $n/2$ סיבובים. לכן הזמן $O(n^2)$ והמקום $O(n)$. אינווריאנט הנכונות אומר שכל סיבוב גמור סימן בדיוק $0$ אחד ו-$1$ אחד; קבלה מתרחשת בדיוק כשלא נשאר סימן בלתי־מותאם.

טעויות נפוצות

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

הצעת המחשה

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

תרגילים

תרגיל 1 — מכריע ל-$0^m1^m$

תארו מכריע חד־סרטי לשפה $\{0^m1^m:m\ge0\}$. הוכיחו נכונות באמצעות אינווריאנט, עצירה, וחסמי זמן ומקום $O(n^2)$ ו-$O(n)$ בהתאמה.

תרגיל 2 — קידוד זוג

הוכיחו כי $(x,y)\mapsto xy$ אינו קידוד זוג תקין. הוכיחו כי $(x,y)\mapsto 0^{|x|}1xy$ חד־משמעי וניתן לפענוח יעיל, וחסמו את אורך הקידוד.

תרגיל 3 — מעבר קונפיגורציה

המכונה במצב $q$, קוראת $0$, כותבת $X$, נעה ימינה ועוברת ל-$r$. כתבו את היורש של $u\,q\,0v$. טפלו במפורש במקרה $v=\varepsilon$.

תרגיל 4 — זמן חוסם מקום; חזרת קונפיגורציה

1. הוכיחו כי מכריע בזמן $t(n)$ משתמש במקום $O(t(n))$.
2. הוכיחו כי במכונה דטרמיניסטית, חזרת קונפיגורציה בריצה גוררת אי־עצירה מאותה נקודה ואילך.

תרגיל 5 — סימולציה דו־סרטית מול חד־סרטית

מכונה דו־סרטית מעתיקה קלט באורך $n$ ואז מבצעת $n$ סריקות של ההעתק. חסמו זמן ומקום. מהו החסם הבטוח שמספק משפט הסימולציה החד־סרטית? מה המשפט אינו טוען?

סיכום

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

תרגול מודרך

משימה 1 — אוניברסליות וכמתים

תיאור מכונה באורך $m$ וקלט באורך $n$. הסבירו מתי תקורת הפענוח רשאית להיבלע בקבוע, ומתי אסור. נסחו את הכמתים.

משימה 2 — השוואת מכונות פלינדרום

מכונה $A$ חד־סרטית מחליטה פלינדרום בסימון זוגות קיצוניים ב-$O(n)$ סיבובים של סריקה $O(n)$. מכונה $B$ דו־סרטית מעתיקה ומשווה מקצוות בזמן $O(n)$. השוו זמן ומקום, וחסמו את סימולציית $B$ לסרט יחיד. קדדו קונפיגורציה של $B$ בעלת $s$ תאי עבודה וחסמו את מספרן.

משימה 3 — רשימת בדיקה למשאבים

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

מקורות

• ראיית סיכום סטודנטים: הסיכום הממוזג, עמ' 1-7, 25-27, 86, 101-106 ו-132; משמש לסדר ולמינוח בלבד.
• ראיית קורס: תמלילי סמסטר א' 2026, שיעורים 1-2.
• אימות: Sipser, מהדורה 3, עמ' 165-181 ו-205-212.
• אימות: Arora-Barak, טיוטה, עמ' 21-42.
• אימות: Papadimitriou, עמ' 19-35.