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

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

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

3. מכונה אוניברסלית

על מנת לייצג מ"ט באופן נוח, נרצה לקודד אותה בצורת מחרוזת מעל הא"ב plot:\[\left\{ {0,1} \right\}\].

דרישות מקידוד של מכונת טיורינג:

  • יהיה ניתן לשחזר את המכונה בהינתן הקידוד שלה.
  • יהיה ניתן "להריץ" את המכונה בהינתן הקידוד שלה.

תהי plot:\[M = \left( {Q,{q_0},F,\Gamma ,\flat ,\Sigma ,\delta } \right)\]. נציע את הקידוד הבא (קיימים עוד קידודים, הבחירה היא שרירותית).

plot:\[Q = \left\{ {1,2,3,...,\left| Q \right|} \right\},{q_0} = 1,F = \left\{ {2,3} \right\},\Sigma  = \left\{ {1,2,...,\left| \Sigma  \right|} \right\},\Gamma  = \left\{ {1,2,...,\left| \Gamma  \right|} \right\},\flat  = \left| \Gamma  \right|\]

הכיוונים יקודדו: plot:\[\left\{ {L,R,S} \right\} = \left\{ {1,2,3} \right\}\].

קידוד של מעברים: יהי אחד המעברים, plot:\[\delta \left( {q,a} \right) = \left( {p,b,d} \right)\]. נקודד את המעבר על ידי המחרוזת הבינארית הבאה: plot:\[{1^q}{01^a}{01^p}{01^b}{01^d}\].

קידוד של המכונה M למחרוזת בינארית יהיה: plot:\[{1^{\left| Q \right|}}{01^{\left| \Gamma  \right|}}{01^{\left| \Sigma  \right|}}00\left\langle {{\delta _1}} \right\rangle 00\left\langle {{\delta _2}} \right\rangle 00...\left\langle {{\delta _m}} \right\rangle 000\]

כאשר כל plot:\[\left\langle {{\delta _i}} \right\rangle \] הוא קידוד של אחד המעברים, וכן plot:\[m = \left( {\left| Q \right| - 2} \right) \cdot \left| \Gamma  \right|\].

עבור מ"ט plot:\[M\] , נסמן את המחרוזת הבינארית המתאימה לה ב-plot:\[\left\langle M \right\rangle \]. בהינתן מחרוזת בינארית, קל לבדוק האם היא מהצורה plot:\[\left\langle M \right\rangle \]. נגדיר כל מחרוזת בינארית שאיננה ניתנת לפירוש לפי הקונבנציה שהגדרנו, כקידוד של מכונה אותה נכנה בשם plot:\[{M_{stam}}\], שעוצרת מייד על כל קלט במצב סופי 2.

קידוד של קלט plot:\[x\] מעל א"ב plot:\[\Sigma \] הוא המחרוזת plot:\[\left\langle x \right\rangle  = {1^{{x_1}}}{01^{{x_2}}}{0...01^{{x_n}}}\].

קידוד של קונפיגורציה plot:\[c = \left( {\alpha ,q,i} \right)\]: plot:\[\left\langle c \right\rangle  = {1^{{\alpha _1}}}{01^{{\alpha _2}}}{0...01^{{\alpha _{i - 1}}}}{001^{{\alpha _i}}}{0...01^{{\alpha _m}}}00\]

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



נגדיר את הפונקציה NEXT:

plot:\[NEXT\left( {\left\langle M \right\rangle ,\left\langle c \right\rangle } \right) = \left\{ {\begin{array}{*{20}{c}}    {\left\langle {c'} \right\rangle ,c\mathop {\mathop  \vdash \limits_{\text{M}} }\limits^1 c'} \hfill & {{\text{the input is valid and also }}c \notin F} \hfill  \\    {{\text{Undefined}}} \hfill & {{\text{Else}}} \hfill  \\ \end{array} } \right.\]

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

קלט של מספר ארגומנטים: עד כה דיברנו על מילת קלט אחת plot:\[w\] עבור מכונת טיורינג. ניתן להרחיב את הגדרת הקלט למספר ארגומנטים כלשהו. נבצע זאת על ידי הוספת הסימן "," לשפה, ושימוש בו כדי להפריד בין מילים שונות.

טענה: הפונקציה NEXT ניתנת לחישוב. כלומר, קיימת מ"ט שעל מילת קלט plot:\[\left\langle m \right\rangle ,\left\langle c \right\rangle \] תוציא את הפלט plot:\[NEXT\left( {\left\langle m \right\rangle ,\left\langle c \right\rangle } \right)\].

הוכחה: נציג בניה של מכונה:

א.      בדוק את חוקיות הקלט. בכל מקרה של אי חוקיות נכנס ללולאה אינסופית.

ב.      אם plot:\[\left\langle c \right\rangle \] הינה סופית, נכנס ללולאה אינסופית.

ג.       אם plot:\[\left\langle M \right\rangle \] מתאים ל-plot:\[{M_{stam}}\]: אם plot:\[\left\langle c \right\rangle \] היא הקונפיגורציה ההתחלתית, אזי plot:\[\left\langle {c'} \right\rangle \] היא קונפיגורציה סופית מתאימה. אחרת אם plot:\[\left\langle c \right\rangle \] לא תחילית, נכנס ללולאה אינסופית (מצב לא חוקי).

ד.      נניח ש-plot:\[c\] חוקית ומתאימה ל-plot:\[M\], אזי נחפש את המצב בו נמצאת המכונה והאותה אותה היא קוראת על ידי חיפוש המחרוזת 00 בקלט plot:\[\left\langle c \right\rangle \]. plot:\[{...001^q}{01^a}0...\]. נחפש בקידוד plot:\[\left\langle M \right\rangle \] מה עושה המכונה בסיטואציה כזו (כלומר מהו plot:\[\delta \left( {q,a} \right)\]) על ידי חיפוש המחרוזת plot:\[{001^q}{01^a}0\] ב-plot:\[\left\langle M \right\rangle \]. נוציא מתוך plot:\[\left\langle M \right\rangle \] את plot:\[p,b,d\]: plot:\[{1^p}{01^b}{01^d}\] ונשנה את plot:\[c\] בהתאם. נקבל plot:\[\left\langle {c'} \right\rangle \] ונוציא אותו כפלט.



הגדרה: הפונקציה האוניברסלית:

plot:\[U\left( {\left\langle M \right\rangle ,\left\langle x \right\rangle } \right) = \left\{ {\begin{array}{*{20}{c}}    {\left\langle {{f_M}\left( x \right)} \right\rangle } \hfill & {{\text{If the input is valid and also }}{f_M}\left( x \right){\text{ is defined}}} \hfill  \\    {{\text{Undefined}}} \hfill & {{\text{Else}}} \hfill  \\ \end{array} } \right.\]

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

טענה: הפונקציה האוניברסלית U ניתנת לחישוב ע"י מכונת טיורינג.

הוכחה: על קלט plot:\[\left\langle m \right\rangle ,\left\langle x \right\rangle \]:

א.      בדיקת חוקיות של הקלט.

ב.      אם plot:\[M = {M_{stam}}\] נוציא פלט plot:\[\varepsilon \].

ג.       נבנה את החישוב של plot:\[M\] על plot:\[x\].

a.      plot:\[\left\langle {{c_0}} \right\rangle  = 00\underbrace 1_{{q_0}}0\left\langle x \right\rangle \]

b.      כל עוד plot:\[c\] הנוכחית איננה סופית: plot:\[\left\langle c \right\rangle  = NEXT\left( {\left\langle M \right\rangle ,\left\langle C \right\rangle } \right)\].

c.      אם מגיעים לקונפיגורציה סופית, נוציא כפלט את תוכן plot:\[\left\langle c \right\rangle \] עד מיקום 00.

מתקיים: אם הקלט לא חוקי או אם M לא עוצרת על הקלט plot:\[x\], המכונה לא עוצרת. אם הקלט חוקי,

ו-plot:\[M\] עוצרת על הקלט plot:\[x\] תוך plot:\[t\] צעדים, אזי נמצא את הפלט על ידי plot:\[t\] הפעלות של NEXT.

הגדרה: כל מ"ט שמחשבת את הפונקציה U נקראת מכונת טיורינג אוניברסלית.

טענה: קיימת מ"ט אוניברסלית.



תגיות המסמך:

לפרק הקודם2.3. מודל ה-RAM
לפרק הבא4. בעיות הכרעה
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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