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

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

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

6.3.1. תרגיל 1

הוכח כי plot:${L_{ = 3}}$ אינה ב-RE או ב-CO-RE.

פתרון: נוכיח את הטענה בשני שלבים:

א.      נראה רדוקציה plot:$HP \leqslant {L_{ = 3}}$ ונסיק ש-plot:${L_{ = 3}}$ אינה ב-CO-RE.

ב.      נראה רדוקציה plot:$\overline {HP}  \leqslant {L_{ = 3}}$ ונסיק ש-plot:${L_{ = 3}}$ אינה ב-RE.

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

לכל קלט plot:$w$, המכונה תריץ ראשית את plot:$M$ על plot:$x$. כאשר plot:$M$ עוצרת, היא תעבור למצב מקבל אם plot:$w$ הינו 1 או 11 או 100.

פונקציה זו הינה רדוקציה:

    1. פונקציה מלאה: לכל plot:$\left\langle M \right\rangle $ ולכל plot:$x$ מוגדר פלט הפונקציה.
    2. פונקציה ניתנת לחישוב: ניתן לבנות מכונה שתריץ את plot:$M$ על plot:$x$, וכן ניתן בפשטות להרכיב עליה מכונה שתקבל עבור הקלטים המבוקשים.
    3. תקפות: נחלק לשני מקרים:

      א. אם plot:$\left( {\left\langle m \right\rangle ,x} \right)$ אינו שייך ל-HP, אזי plot:${M_x}$ הינה מכונה שלא תעצור, והשפה

          המתאימה לה היא השפה הריקה, ומכאן plot:$\left\langle {{M_x}} \right\rangle  \notin {L_{ = 3}}$.

      ב. אם plot:$\left( {\left\langle m \right\rangle ,x} \right)$ שייך ל-HP, אזי plot:${M_x}$ היא מכונה שמקבלת עבור אחד משלושת הקלטים 1,11,100. מתקיים כי plot:$\left\langle {{M_x}} \right\rangle  \in {L_{ = 3}}$.



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

הראנו רדוקציה plot:$HP \leqslant {L_{ = 3}}$ומכאן plot:${L_{ = 3}}$ אינה ב-CO-RE.



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

פעולת plot:${M_x}$ תוגדר באופן הבא: עבור קלט plot:$w$: אם plot:$w = 1$ או plot:$w = 10$ או plot:$w = 110$ אזי המכונה עוצרת ומקבלת. אחרת המכונה מריצה את plot:$M$ על plot:$x$. כאשר plot:$M$ עוצרת, המכונה מקבלת את plot:$w$.

נטען שפונקציה זו הינה רדוקציה:

    1. פונקציה מלאה: לכל plot:$\left\langle M \right\rangle $ ולכל plot:$x$ מוגדר פלט הפונקציה.
    2. פונקציה ניתנת לחישוב: ניתן לממש פונקציה כזו על ידי פעולת קומפילציה פשוטה.
    3. תקפות: לא נוכיח את התקפות באופן פורמלי, אך נביט בשפה המוגדרת על ידי plot:${M_x}$:

      השפה plot:$L\left( {{M_x}} \right)$ הינה plot:$\left\{ {1,10,110} \right\}$ אם plot:$\left( {\left\langle m \right\rangle ,x} \right) \in \overline {HP} $. אחרת, השפה תהיה plot:${\Sigma ^*}$.

הראנו רדוקציה plot:$\overline {HP}  \leqslant {L_{ = 3}}$ומכאן plot:${L_{ = 3}}$ אינה ב-RE.

תגיות המסמך:

לפרק הקודם6.3. תמונת העולם
לפרק הבא6.3.2. תרגיל 2
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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