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

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

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

2.1. דוגמאות

הגדרה: מכונת טיורינג חסרת מנוחה היא מכונה שהגדרתה זהה לזו של מכונת טיורינג, מלבד פונקצית המעברים שתוגדר כך: plot:\[\delta :\left( {Q\backslash F} \right) \times \Gamma  \to \left( {Q \times \Gamma  \times \left\{ {L,R} \right\}} \right)\].

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

טענה: מודל מ"ט חסרת מנוחה שקול למודל מ"ט.

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

נראה כי כל מ"ט ניתנת לייצוג כמ"ט חסרת מנוחה כך: תהי M מ"ט. עבור כל צעד מהצורה plot:\[{\delta _1}\left( {q,a} \right) = \left( {p,b,L} \right)\] או מהצורה plot:\[{\delta _1}\left( {q,a} \right) = \left( {p,b,R} \right)\], יתקיים plot:\[{\delta _2}\left( {q,a} \right) = {\delta _1}\left( {q,a} \right)\]. עבור צעדים מהצורה plot:\[{\delta _1}\left( {q,a} \right) = \left( {p,b,S} \right)\] נגדיר שני מצבים: plot:\[{\delta _2}\left( {q,a} \right) = \left( {p',b,R} \right)\] וכן plot:\[\forall c \in \Gamma \] נגדיר plot:\[{\delta _2}\left( {p',c} \right) = \left( {p,c,L} \right)\]. כלומר, המכונה תעבור על ידי מעבר ימינה למצב עזר אותו אנחנו מגדירים, ומיד לאחר מכן תבצע צעד שמאלה מבלי לשנות את הקלט.

ניתן להוכיח באינדוקציה כי בנייה זו אכן שקולה למ"ט.

הגדרה: מודל מ"ט עם plot:\[k\] סרטים הינו מודל הזהה למ"ט, מלבד פונקצית המעברים שתוגדר plot:\[\delta :\left( {Q\backslash F} \right) \times {\Gamma ^k} \to Q \times {\Gamma ^k} \times {\left\{ {L,R,S} \right\}^k}\]. מכונה זו הינה בעלת plot:\[k\] ראשים קוראים-כותבים.

טענה: לכל plot:\[k \geqslant 1\], מודל מ"ט עם plot:\[k\] סרטים שקול למודל מ"ט רגיל.

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

  • מודלים חלשים יותר: אוטומט סופי, אוטומט מחסנית.
  • מודלים עם אלמנטים אינסופיים – למשל מ"ט עם plot:\[\infty \] מצבים.


התזה של Church: כל מודל כללי וסביר של מ"ט שקול בכוחו לכוחה של מ"ט.

כללי: מודל חזק לפחות כמו מ"ט. סביר: מודל שבו לכל אובייקט תיאור סופי.

תגיות המסמך:

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

החלק הראשון

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

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

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

מאת: חשוון

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