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

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

1.2. מכונת טיורינג

מ"ט היא השביעיה $plot:[M = left( {Q,{q_0},F,Gamma ,flat ,Sigma ,delta } ight)]$ כאשר:

plot:[Q] : קבוצה סופית של מצבים.

$plot:[{q_0} in Q]$ : מצב התחלתי.

plot:[F subseteq Q] : קבוצת מצבים סופיים.

plot:[Sigma ] : קבוצה סופית של אותיות המכונה א"ב הקלט.

plot:[Gamma ] : קבוצה סופית של אותיות המכונה א"ב עבודה. מתקיים כי plot:[Sigma subseteq Gamma ] .

plot:[flat ] : סימן רווח המקיים plot:[flat in Gamma ackslash Sigma ] .

plot:[delta ] : פונקצית המעברים: plot:[delta :left( {left( {Qackslash F}
ight) imes Gamma }
ight) o
left( {Q imes Gamma imes left{ {L,R,S}
ight}}
ight)] . plot:[left{ {L,R,S}
ight}] הם סימנים המייצגים את כיוון תנועת הראש הקורא (שמאלה, ימינה או עמידה במקום). דוגמא: $plot:[delta left( {{q_1},0} ight) = left( {{q_2},1,R} ight)]$ משמעותו: "אם במצב $plot:[{q_1}]$ רואים plot:[0] , אז עוברים למצב $plot:[{q_2}]$ , כותבים 1 במקום עליו מצביע הראש, ומזיזים את הראש תא אחד ימינה".

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

המכונה מתחילה תמיד את החישוב על קלט $plot:[x in {Sigma ^*}]$ במצב הבקרה $plot:[{q_0}]$ כאשר הראש מצביע לתא השמאלי ביותר בסרט. בקצה השמאלי של הסרט רשומה מילת קלט plot:[x] , ואחריה אינסוף plot:[flat ] -ים.

הריצה מתבצעת בצעדי חישוב על פי פונקצית המעברים plot:[delta ] . בכל צעד חישוב המכונה מבצעת פעולה התלויה במצב הבקרה בו היא נמצאת ובתוכן התא שעליו מצביע הראש.

במקרה בו הראש מצביע על התא השמאלי ביותר בקלט, ובפונקצית המעברים מסומן לנוע שמאלה, הראש יישאר בצעד הבא במקומו. הריצה על הקלט plot:[x] מסתיימת כאשר המכונה נכנסת למצב סופי (מצב השייך לקבוצה plot:[F] ). במקרה הנ"ל נאמר כי המכונה עוצרת על . לא מובטח כי חישוב המכונה יעצור לכל קלט!

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

קונפיגורציה רגעית של מכונת טיורינג היא שלישיה $plot:[c in {Gamma ^*} imes Q imes mathbb{N}]$ . השלישיה plot:[c = left( {alpha ,q,i}
ight)] מתארת את מצב המכונה ברגע מסויים במהלך החישוב שלה: plot:[alpha ] מתאר את תוכן הסרט, plot:[q] מתאר את מצב הבקרה, ו- plot:[i] מציין את מיקום הראש (אינדקס התא עליו מצביע הראש). המחרוזת מתארת את תוכן הסרט מהקצה השמאלי עד המקום האחרון שאינו plot:[flat ] .

הקונפיגורציה ההתחלתית של מכונת טיורינג על קלט $plot:[x in {Sigma ^*}]$ היא $plot:[left( {x,{q_0},0} ight)]$ .

קונפיגורציה סופית של מ"ט היא קונפיגורציה plot:[left( {eta gamma ,q,i}
ight)] כאשר $plot:[eta ,gamma in {Gamma ^*},q in F]$ וגם plot:[left| eta
ight| = i] . במקרה זה נאמר כי plot:[eta ] הוא הפלט המתאים לקונפיגורציה סופית זו.

צעד חישוב של מ"ט הוא מעבר מקונפיגורציה רגעית אחת לקונפיגורציה רגעית שניה, לפי פונקצית המעברים plot:[delta ] . תהי מכונה plot:[M] הנמצאת בקונפיגורציה plot:[c = left( {alpha ,q,i}
ight)] . נניח כי $plot:[{alpha _i} = a]$ וכי plot:[delta left( {q,a}
ight) = left(
{p,b,d in left{ {L,R,S}
ight}}
ight)] , אז המכונה מבצעת את הצעדים הבאים:

כותבת את האות במקום האות .
משנה את מצב הבקרה מ- ל-.
מזיזה את הראש בהתאם לאות: =לא מזיזה, =למקום , =למקום . (אם לא זזים).

קונפיגורציה עוקבת: הקונפיגורציה העוקבת plot:[c'] של הקונפיגורציה הנוכחית plot:[c] תוגדר באופן יחיד על ידי ביצוע צעד חישוב על הקונפיגורציה הנוכחית. נסמן: $plot:[cmathop {mathop vdash limits_{ ext{M}} }limits^1 c']$ .

חישוב פונקציות: בהינתן מ"ט plot:[M] , הפונקציה $plot:[{f_M}]$ שהמכונה מחשבת היא פונקציה (חלקית או מלאה) מ- $plot:[{Sigma ^*}]$ ל- $plot:[{Gamma ^*}]$ , המוגדרת רק על קלטים שעליהם החישוב של עוצר. ערך הפונקציה $plot:[{f_M}]$ על קלטים כאלו הוא הפלט שמכונה מוציאה בחישוב, כלומר לכל קלט $plot:[x in {Sigma ^*}]$ , אם plot:[M] עוצרת על plot:[x] עם פלט plot:[y] , אזי $plot:[{f_M}left( x ight) = y]$ , ואחרת $plot:[{f_M}]$ אינה מוגדרת על המחרוזת .

הערה: כאשר מגדירים פונקצית מעברים plot:[delta ] , גם אם יש מצבים אליהם לא נגיע, חובה להגדיר אותם (באופן שרירותי כלשהו כרצוננו) מכיוון ש- היא לפי הגדרתה פונקציה מלאה.

לפרק הקודם1. מבוא

לפרק הבא2. שקילות של מודלים

מאת: דנה

6/7/2010 18:01

החלק הראשון

בבקשה

מאת: אני

19/6/2010 18:47

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299

מאת: רועי

8/6/2010 21:53

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

מאת: חשוון

4/4/2010 17:25

מתי המסמך יחזור?

דיווח על הפרת זכויות יוצרים

תוכן העניינים:

מבוא

מכונת טיורינג

שקילות של מודלים

תרגיל

מודל ה-RAM

רדוקציות

שפות שאינן כריעות

חישוב פונקציות

בעיות חיפוש

קישורים רלוונטיים:

מדעי המחשב

שיתוף:

| עוד

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

פרוייקט UnderWarrior - מדריכים, מאמרים, סיכומים וחומרי לימוד בתחומי תכנות, מתמטיקה, אבטחת מידע ועוד
1997-2024 © כל הזכויות שמורות לניר אדר