תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מהלך חישוב |
דוגמא |
||
שורה 31:
נגדיר מצב קצה: נניח שראש המכונה נמצא בתא השמאלי ביותר (בתא הראשון), והמכונה צריכה להזיז את הראש שמאלה (הפונקציה <math>\delta</math> החזירה תזוזה L, שמאלה). במקרה זה נגדיר שהראש נשאר במקומו (במקום לזוז שמאלה), והחישוב ממשיך כרגיל. לעיתים מכונה מקרה זה בשם '''נסיון נפילה מן הסרט'''.
==דוגמא==
נבנה מכונת-טיורינג שמוסיפה את התו "0" לתחילת הקלט, כלומר, עבור הקלט <math>x_1x_2\cdots x_n</math> הפלט יהיה <math>0x_1x_2\cdots x_n</math>. נניח כי הקלט הינו בינארי, <math>\Sigma=\{0,1\}</math>. למכונה יש למעשה שתי משימות: האחת, להוסיף "0" בתור התו הראשון, והשניה "להזיז" את הקלט מיקום אחד ימינה על סרט הזיכרון. נשתמש בשלושה מצבים: המצב הראשון "ישתול" את התו '0' בתחילה, ו"יזכור" מה היה רשום בתא לפני שדרסנו אותו. שני המצבים הבאים יסמלו את התו שאנחנו "זוכרים", ותפקידם להעתיק את התו צעד אחד ימינה, כאשר כעת "זוכרים" את התו שנדרס בצעד זה, וחוזר חלילה. מצב רביעי יציין סיום של המכונה, ואליו נגיע כאשר העתקנו את המידע ש"זכרנו" אל תא ריק.
באופן פורמלי, מרכיבי המכונה הם:
<div style="direction: ltr;">
*<math>Q=\{start , mem_0, mem_1, done\}</math>
* <math>q_0 = start</math>
* <math> F=\{ done \}</math>
* <math> \Gamma=\{0,1,\sqcup\}</math>
* <math> \Sigma = \{0,1\}</math>
</div>
ופונקצית המעברים מוגדרת להלן
<center>
{| class="wikitable"
|-
! <math>\sqcup</math> !! 1 !! 0 !! <math>\delta(\cdot,\cdot)</math>
|-
| <math>done, 0, R</math> || <math>mem_1,0,R</math> || <math>mem_0,0,R</math> || <math>start</math>
|-
| <math>done,0,R</math> || <math>mem_1,0,R</math> || <math>mem_0,0,R</math> || <math>mem_0</math>
|-
| <math>done,1,R</math> || <math>mem_1,1,R</math> || <math>mem_0,1,R</math> || <math>mem_1</math>
|}
</center>
העמודות הינן האות הנוכחית, והשורות הינו המצב הנוחכי. ערך כל תא מסמל את המצב החדש אליו אנו עוברים, האות אותה אנו כותבים וכיוון תנועת הראש. למשל <math>\delta(start,0)=(mem_0,0,R)</math>. נשים לב שהמצב התחילי start והמצב <math>mem_0</math> מבצעים את אותה פעולה, ואפשר לאחד אותם למצב יחיד (ואכן, בתחילת הריצה אנחנו "זוכרים" לכתוב 0, בדיוק כאמור במצב <math>mem_0</math>).
[[קטגוריה:תורת החישוביות]]
| |||