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

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

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

5.4. שימוש ברדוקציה – הוכחה ששפה אינה ב-CO-RE / RE

כאשר נתונה שפה L וברצוננו להראות כי L איננה ב-CO-RE, נוכל להשתמש ברדוקציה.

כלל אצבע: את רוב השפות שאינן ב-CO-RE ניתן להוכיח שאינן ב-CO-RE על ידי רדוקציה מ-HP.

על מנת להוכיח ששפה איננה ב-RE, נראה רדוקציה מ-plot:$\overline {{\text{HP}}} $.

דוגמא: נביט בשפה הבאה: plot:$L = \left\{ {\left\langle M \right\rangle :{f_M}\left( \varepsilon  \right) = \varepsilon } \right\}$. האם שפה זו שייכת ל-R? האם היא שייכת

ל-RE?

פתרון: נגדיר את הפונקציה plot:$f$ הבאה: plot:$f\left( {\left\langle M \right\rangle ,x} \right) = \left\langle {{M_x}} \right\rangle $.

נגדיר את plot:${M_x}$ כך:

א. המכונה מתנהגת באופן שרירותי עבור כל קלט שאינו plot:$\varepsilon $.

ב. עבור קלט שהוא plot:$\varepsilon $, המכונה מריצה את plot:$M$ על plot:$x$. כאשר plot:$M$ עוצרת על plot:$x$, המכונה תפלוט plot:$\varepsilon $.



טענה: הפונקציה plot:$f$ הינה רדוקציה plot:$HP \leqslant L$:

  • הפונקציה מלאה: עבור כל קלט, מוגדרת מהי התוצאה של הפונקציה.
  • הפונקציה ניתנת לחישוב: ע"י פעולת קומפילציה פשוטה ניתן ליצור פונקציה המתנהגת כמתואר.
  • תקפות:

א.      ניקח איבר plot:$\left( {\left\langle M \right\rangle ,x} \right)$  השייך ל-HP. נבנה את plot:$\left\langle {{M_x}} \right\rangle $ המתאימה לו. מכיוון שהאיבר שייך ל-HP, אז כאשר נריץ את plot:$\left\langle {{M_x}} \right\rangle $ עם plot:$\varepsilon $ היא תעצור ותפלוט plot:$\varepsilon $.

ב.      ניקח איבר plot:$\left( {\left\langle M \right\rangle ,x} \right)$  שאינו שייך ל-HP. נבנה את plot:$\left\langle {{M_x}} \right\rangle $ המתאימה לו. מכיוון שהאיבר אינו שייך ל-HP, אז כאשר נריץ את plot:$\left\langle {{M_x}} \right\rangle $ עם plot:$\varepsilon $ היא לעולם לא תעצור.

ניתן לראות כי אכן מתקיימת התקפות.

הראנו plot:$HP \leqslant L$. מכיוון ש-HP איננה שייכת ל-CO-RE, ולפי משפט הרדוקציה, נקבל כי L אינה שייכת אף היא ל-CO-RE.

נסכם את מה שעשינו:

  1. רצינו להראות כי שפה L אינה ב-CO-RE.
  2. הראנו רדוקציה plot:$HP \leqslant L$.
  3. מ-plot:$HP \leqslant L,HP \notin {\text{CO - RE}}$ הגענו למסקנה: plot:$L \notin {\text{CO - RE}}$.

הערה: ניתן להשתמש גם בטרנזיטיביות להוכחה דומה.

נניח כי עבור שפה L מתקיים כי plot:${L_2} \leqslant L$ וגם plot:$HP \leqslant {L_2}$, אזי מהטרנזיטיביות נובע כי plot:$HP \leqslant L$ ושוב נוכל להגיע למסקנה כי plot:$L \notin {\text{CO - RE}}$.



תגיות המסמך:

לפרק הקודם5.3. תכונות של רדוקציות
לפרק הבא6. שפות שאינן כריעות
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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