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

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

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

6.2. משפט Rice

הגדרה: תכונה של שפות RE היא קבוצת שפות plot:\[S \subseteq {\text{RE}}\]. תכונה תיקרא תכונה טריויאלית אם מתקיים plot:\[S = \Phi \] או plot:\[S = {\text{RE}}\].

סימון: עבור תכונה S, נגדיר את הסימון הבא: plot:\[{L_S} \triangleq \left\{ {\left\langle M \right\rangle |L\left( M \right) \in S} \right\}\].

plot:${L_s}$ היא שפה המכילה את קידודי כל מכונות טיורינג שהשפות שהן מקבלות שייכות ל-plot:$S$.

אבחנה: אם S טריויאלית אז plot:\[{L_S} \in {\text{R}}\].

משפט Rice: לכל תכונה לא טריויאלית plot:\[S\] נובע כי plot:\[{L_S} \notin R\].

דוגמאות לשימושים במשפט:

  1. נגדיר את השפה plot:\[{L_\varepsilon } = \left\{ {\left\langle M \right\rangle |\varepsilon  \in L\left( M \right)} \right\}\]. plot:\[{L_\varepsilon }\] היא שפה המתאימה לתכונה plot:\[{L_{{S_1}}} = {L_\varepsilon }\].

    plot:\[{S_1}\] איננה תכונה טריויאלית: קיימות שפות ב-RE המקיימת את plot:\[{S_1}\]: plot:\[{\Sigma ^*},\left\{ \varepsilon  \right\},...\], וכמו כן קיימות שפות ב-RE שאינן מקיימות את plot:\[{S_1}\]: plot:\[\phi ,\left\{ {1111} \right\},...\].

    מכאן לפי משפט Rice: plot:\[{L_\varepsilon } = {L_{{S_1}}} \notin R\].
  2. plot:\[{L_2} = \left\{ {\left\langle M \right\rangle |L\left( M \right){\text{ is final}}} \right\} \notin {\text{R}}\].
  3. plot:\[{L_{{\Sigma ^*}}} = \left\{ {\left\langle M \right\rangle |L\left( M \right) = {\Sigma ^*}} \right\} \notin R\].

משפט Rice 2: תהי S תכונה לא טריויאלית המקיימת plot:\[\phi  \in S\], אזי מתקיים: plot:\[{L_S} \notin {\text{RE}}\].



כיצד משתמשים במשפט Rice כדי להוכיח ששפה אינה ב-R?

נגדיר תכונה plot:$S$ ונוכיח שמתקיים:

  1. קיימת plot:$L' \in RE$ כך ש-plot:$L' \notin S$ (ומכאן plot:$S \ne RE$).
  2. קיימת plot:$L'' \in RE$ כך ש-plot:$L'' \in S$ (ומכאן plot:$S \ne \phi $).
  3. נראה כי plot:${L_S} = L$.

נסיק כי plot:$L \notin R$.

מתי לא נשתמש במשפט Rice?

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

    דוגמא: plot:${L_A} = \left\{ {\left( {\left\langle {{M_1}} \right\rangle ,\left\langle {{M_2}} \right\rangle } \right)|\left| {L\left( {{M_1}} \right) \cap L\left( {{M_2}} \right)} \right| = 3} \right\}$.

    קל למצוא רדוקציה מ-plot:${L_{ = 3}} \leqslant {L_A}$, לדוגמא: plot:$f\left( {\left\langle M \right\rangle } \right) = \left( {\left\langle M \right\rangle ,\left\langle M \right\rangle } \right)$ אולם בעייתי להשתמש עבור שפה זו במשפט Rice.
  2. כאשר התכונה היא תכונה של מכונה ולא של שפה. למשל: שפת קידודי כל המכונות העוצרות על הפלט הריק.

    לכל שפה ב-RE שאינה מכילה את plot:$\varepsilon $ יש מ"ט שמקבלת אותה וגם עוצרת על plot:$\varepsilon $ ויש מ"ט שמקבלת אותה ולא עוצרת על plot:$\varepsilon $ ולכן התכונה תלויה במכונה ולא בשפה.
  3. כאשר התכונה טריויאלית. לדוגמא: plot:$L = \{ \left\langle M \right\rangle |\underbrace {L\left( M \right)}_{ \in RE} = \underbrace {\overline {HP} }_{ \notin RE}\}  = \phi $



תגיות המסמך:

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

החלק הראשון

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

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

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

מאת: חשוון

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