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

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

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

5.2. משפט הרדוקציה

תהינה plot:\[{L_1},{L_2}\] שפות כלשהן כך שמתקיים plot:\[{L_1} \leqslant {L_2}\], אזי:

  1. אם plot:\[{L_1} \in R \Leftarrow {L_2} \in R\]                      (באופן שקול: אם plot:\[{L_2} \notin {\text{R}} \Leftarrow {L_1} \notin {\text{R}}\])
  2. אם plot:\[{L_1} \in RE \Leftarrow {L_2} \in RE\]                  (באופן שקול: אם plot:\[{L_2} \notin {\text{RE}} \Leftarrow {L_1} \notin {\text{RE}}\])
  3. אם plot:\[{L_1} \in {\text{CO - RE}} \Leftarrow {L_2} \in {\text{CO - RE}}\]   (באופן שקול: אם plot:\[{L_2} \notin {\text{CO - RE}} \Leftarrow {L_1} \notin {\text{CO - RE}}\]).

הערה: לרוב נשתמש במשפטים אלו כדי להוכיח כי שפות אינן ב-plot:\[{\text{R}},{\text{RE}},{\text{CO - RE}}\].

הוכחת 1.

plot:$ \Leftarrow {L_1} \leqslant {L_2}$קיימת פונקציה plot:$f$ המהווה רדוקציה מ-plot:${L_1}$ ל-plot:${L_2}$ ובפרט קיימת מ"ט plot:${M_f}$ המחשבת אותה (ניתנת לחישוב). בנוסף מכיוון ש-plot:$f$ מלאה, plot:${M_f}$ עוצרת תמיד.

plot:$ \Leftarrow {L_2} \in R$ קיימת plot:${M_2}$ שעוצרת תמיד ו-plot:$L\left( {{M_2}} \right) = {L_2}$. נבנה מ"ט plot:${M_1}$ עבור plot:${L_1}$ על קלט plot:$x$:

  1. המכונה משתמשת ב-plot:${M_f}$ על מנת לחשב את plot:$f\left( x \right)$.
  2. המכונה מריצה את plot:${M_2}$ על plot:$f\left( x \right)$. אם plot:${M_2}$ מקבלת/דוחה, plot:${M_1}$ עושה כמוה.

מתקיים:

  • plot:${M_1}$ עוצרת תמיד (כי plot:${M_f},{M_2}$ עוצרות תמיד).
  • plot:$f\left( x \right) \in {L_2} \Leftrightarrow x \in {L_1}$ (עקב תקפות plot:$f$) ומכאן מנכונות plot:${M_2}$ נובע כי גם plot:${M_1}$עוצרת ומקבלת על plot:$x$.
  • plot:${M_2} \Leftarrow f\left( x \right) \notin {L_2} \Leftarrow x \notin {L_1}$ דוחה את plot:$f\left( x \right)\${M_1} \Leftarrow $ דוחה את plot:$x$.


תגיות המסמך:

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

החלק הראשון

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

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

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

מאת: חשוון

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