הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

2.2.1. תרגיל

הוכח כי לכל מ"ט plot:\[M\] קיימת מ"ט plot:\[M'\] המחשבת את אותה פונקציה, אשר אינה מנסה ליפול מהסרט (על ידי נסיון ללכת שמאלה כאשר הראש נמצא בתא השמאלי ביותר בסרט).

פתרון:

נגדים בניה של מכונה אשר לא מנסה ליפול מהסרט:

נגדיר plot:\[\Sigma ',\Gamma '\] בצורה הבאה: שעבור כל אות plot:\[\sigma \] ב-plot:\[\Sigma \] או ב-plot:\[\Gamma \] נגדיר אות מקבילה plot:$\sigma '$.

האלגוריתם:

אתחול: המכונה תחליף את האות הראשונה plot:$\sigma $ באות המקבילה plot:$\sigma '$.

ריצה: במהלך החישוב, בכל פעם שהמכונה נתקלת באות השייכת ל-plot:$\Gamma '$, היא תדע שהיא נמצאת בתא הראשון בסרט, ולכן היא תפעל על פי הכללים הבאים:

  1. אם במקור plot:$M$ הייתה אמורה ללכת שמאלה, אז plot:$M'$ תישאר באותו המקום (ולא תפנה שמאלה).
  2. אם plot:$M$ אמורה להחליף את האות plot:${\sigma _1}$ באות plot:${\sigma _2}$ אז plot:$M'$ תחליף את plot:${\sigma _1}'$ באות plot:${\sigma _2}'$.

סיום:

אם plot:$M$ הגיעה למצב מקבל אז plot:$M'$ צריכה לסמן את המקום ב-$, לנוע שמאלה עד התחלת הסרט, שם היא תמצא אות השייכת ל-plot:$\Gamma '$. את אות זו היא תחליף אותה באות המתאימה מ-plot:\[\Gamma \], תנוע חזרה ימינה עד לסימן ה-$ ותעצור.

בהינתן plot:\[M = \left( {Q,{q_0},F,\Gamma ,\flat ,\Sigma ,\delta } \right)\], נגדיר את plot:\[M'\] כך:

פונקצית המעברים plot:$\delta '$:

  • מעבר התחלתי: plot:$\delta '\left( {{q_{02}},\sigma  \in \Gamma } \right) = \left( {{q_0},\sigma ',S} \right)$
  • plot:$\delta '\left( {q \in Q,\sigma  \in \Gamma } \right) = \delta \left( {q,\sigma } \right)$ - אם לא נמצאים על האות הראשונה, מבצעים את מה שביצעה המכונה המקורית.
  • אם plot:$\delta \left( {q \in Q\backslash F,a} \right) = \left( {p,b,X} \right)$ כך ש plot:$X \in \left\{ {L,S} \right\}$ אז plot:$\delta '\left( {q,a' \in \Gamma '} \right) = \left( {p,b' \in \Gamma ',S} \right)$ - אם נמצאים באות הראשונה, והתנועה המקורית הייתה שמאלה או עצירה, אז נשארים במקום. בכל מקרה, האות שכותבים שייכת ל-plot:\[\Gamma '\].
  • אם plot:$\delta \left( {q,a} \right) = \left( {p,b,R} \right)$ אז plot:$\delta '\left( {q,a' \in \Gamma '} \right) = \left( {p,b' \in \Gamma ',R} \right)$ - אם נמצאים באות הראשונה, והתנועה המקורית הייתה ימינה, אז נעים ימינה, אבל האות שכותבים היא מ-plot:$\Gamma '$.
  • plot:$\delta '\left( {q \in F,\sigma  \in \Gamma } \right) = \left( {{q_L},\$ ,R} \right)$ - אם המכונה הקודמת עצרה, ולא על התו הראשון, אז מחליפים את התו ב-plot:$\$ $ ועוברים למצב שממנו מתחילים לנוע שמאלה.
  • plot:$\delta '\left( {{q_L},\sigma  \in \Gamma } \right) = \left( {{q_L},\sigma ,L} \right)$ - נעים שמאלה בלי לשנות כלום.
  • plot:$\delta '\left( {{q_L},\sigma ' \in \Gamma '} \right) = \left( {{q_R},\sigma  \in \Gamma ,R} \right)$ - מחליפים את האות מ-plot:$\Gamma '$ לאות מ-plot:$\Gamma $ ועוברים למצב שממנו מתחילים לנוע ימינה.
  • plot:$\delta '\left( {{q_R},\sigma  \in \Gamma } \right) = \left( {{q_R},\sigma ,R} \right)$ - נעים ימינה בלי לשנות כלום.
  • plot:$\delta '\left( {{q_R},\$ } \right) = \left( {{q_F},\$ ,S} \right)$ - עצירה.
  • plot:$\delta '\left( {q \in F,\sigma ' \in \Gamma '} \right) = \left( {{q_f},\$ ,S} \right)$ - אם החישוב המקורי נעצר על האות הראשונה, אז עוצרים באותו המקום, ומחזירים כפלט מילה ריקה.



תגיות המסמך:

לפרק הקודם2.2. שיטת ההוכחה של שקילות
לפרק הבא2.3. מודל ה-RAM
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד