5.4. שימוש ברדוקציה – הוכחה ששפה אינה ב-CO-RE / REכאשר נתונה שפה L וברצוננו להראות כי L איננה ב-CO-RE, נוכל להשתמש ברדוקציה. כלל אצבע: את רוב השפות שאינן ב-CO-RE ניתן להוכיח שאינן ב-CO-RE על ידי רדוקציה מ-HP. על מנת להוכיח ששפה איננה ב-RE, נראה
רדוקציה מ- דוגמא:
נביט בשפה הבאה: פתרון:
נגדיר את הפונקציה נגדיר את א. המכונה מתנהגת באופן שרירותי עבור כל
קלט שאינו ב. עבור קלט שהוא טענה: הפונקציה
א.
ניקח איבר ב.
ניקח איבר ניתן לראות כי אכן מתקיימת התקפות. הראנו נסכם את מה שעשינו:
הערה: ניתן להשתמש גם בטרנזיטיביות להוכחה דומה. נניח כי עבור שפה L מתקיים כי תגיות המסמך: |
תוכן העניינים:
קישורים רלוונטיים:שיתוף: |
החלק הראשון
בבקשה