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

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

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

6.3.2. תרגיל 2

הוכח כי plot:${L_{{\Sigma ^*}}} = \left\{ {\left\langle M \right\rangle |L\left( M \right) = {\Sigma ^*}} \right\}$ אינה ב-RE ואינה ב-CO-RE.



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

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

    1. פונקציה מלאה: לכל plot:$\left\langle M \right\rangle $ ולכל plot:$x$ מוגדר פלט הפונקציה.
    2. פונקציה ניתנת לחישוב: ניתן לממש פונקציה כזו על ידי פעולת קומפילציה פשוטה.
    3. תקפות: עבור plot:$\left( {\left\langle M \right\rangle ,x} \right) \in HP$ מתקיים כי המכונה תקבל כל מילה plot:$w$, ולכן קידוד המכונה שייך ל-plot:${L_{{\Sigma ^*}}}$. עבור plot:$\left( {\left\langle M \right\rangle ,x} \right) \notin HP$ מתקיים כי המכונה אינה עוצרת ולכן קידודה אינו שייך ל-plot:${L_{{\Sigma ^*}}}$.

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

ב.      נגדיר את הפונקציה הבאה: plot:$f\left( {\left\langle M \right\rangle ,x} \right) = \left\langle {{M_x}} \right\rangle $. פעולת plot:${M_x}$ על קלט plot:$w$ תוגדר באופן הבא: plot:${M_x}$ מריצה את plot:$x$ על plot:$M$ למשך plot:$\left| w \right|$ צעדים. אם plot:$M$ לא עצרה על plot:$x$, plot:${M_x}$ מקבלת את plot:$w$. אם plot:$M$ עצרה על plot:$x$, אז plot:${M_x}$ דוחה את plot:$w$ או נכנסת ללולאה אינסופית.

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

הראנו רדוקציה plot:$\overline {HP}  \leqslant {L_{{\Sigma ^*}}}$ומכאן plot:\[{L_{{\Sigma ^*}}}\] אינה ב-RE.



תגיות המסמך:

לפרק הקודם6.3.1. תרגיל 1
לפרק הבא7. חישוב פונקציות
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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