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

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

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

6.1. קיום שפות שאינן כריעות

טענה: קיימות שפות שאינן ב-R (וכן נטען גם טענה חזקה יותר: קיימות שפות שאינן ב-RE).

הוכחה: נטען כי מתקיים:

plot:\[\left| {{\text{RE}}} \right| \leqslant \left| {{\text{Tuiring Machines Set}}} \right| \leqslant \left| {\left\{ {w|w \in {{\left\{ {0,1} \right\}}^*} \wedge \left| w \right| \in \mathbb{N}} \right\}} \right| < \left| {\left\{ {L|\forall w \in L,w \in {{\left\{ {0,1} \right\}}^*}} \right\}} \right|\]

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

המעבר השני יבוצע על ידי התאמת plot:\[\left\langle M \right\rangle \] לכל plot:\[M\]. המעבר השלישי נכון מכיוון ש-plot:\[\left| \mathbb{N} \right| < \left| \mathbb{R} \right|\].

טענה: plot:\[\overline {{L_D}}  \notin R\].

מסקנה: plot:\[\overline {{L_u}} ,\overline {{\text{HP}}}  \notin {\text{R}} \Leftarrow {L_u},{\text{HP}} \notin {\text{R}} & \mathop  \Leftarrow \limits_{{L_D} \leqslant HP}^{{L_D} \leqslant {L_u}} {L_D} \notin {\text{R}}\].

טענה: plot:\[\overline {{L_D}}  \notin {\text{RE}}\].

הוכחה: נניח בשלילה כי plot:\[\left\{ {\left\langle M \right\rangle |\left\langle M \right\rangle  \notin L\left( M \right)} \right\} = \overline {{L_D}}  \in {\text{RE}}\], אזי קיימת מכונת טיורינג plot:\[{M_D}\] כך שמתקיים plot:\[L\left( {{M_D}} \right) = \overline {{L_D}} \].

מכאן: קיים plot:\[\left\langle {{M_D}} \right\rangle \]. נרצה לבדוק האם plot:\[\left\langle {{M_D}} \right\rangle  \in \overline {{L_D}} \].

נניח שכן, אזי plot:\[\left\langle {{M_D}} \right\rangle  \in \overline {{L_D}} \], ומכאן לפי הגדרת plot:\[\overline {{L_D}} \]  מתקיים plot:\[\left\langle {{M_D}} \right\rangle  \notin L\left( {{M_D}} \right)\], כלומר plot:\[\left\langle {{M_D}} \right\rangle  \notin \overline {{L_D}} \], בסתירה להנחה. בכיוון השני, אם נניח כי plot:\[\left\langle {{M_D}} \right\rangle  \notin \overline {{L_D}} \] אזי plot:\[\left\langle {{M_D}} \right\rangle  \in L\left( {{M_D}} \right)\], כלומר plot:\[\left\langle {{M_D}} \right\rangle  \in \overline {{L_D}} \], שוב בסתירה להנחה. מכאן שהטענה נכונה. מ.ש.ל.

הגדרה: שפה plot:\[L\] נקראת RE שלמה אם היא מקיימת:

  1. plot:\[L \in {\text{RE}}\].
  2. plot:\[\forall L' \in {\text{RE}},L' \leqslant L\].


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

טענה: plot:\[{L_u}\] היא RE שלמה (ולכן גם HP היא RE שלמה).

תגיות המסמך:

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

החלק הראשון

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

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

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

מאת: חשוון

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