6.3.1. תרגיל 1
הוכח כי
אינה ב-RE או ב-CO-RE.
פתרון: נוכיח
את הטענה בשני שלבים:
א.
נראה רדוקציה
ונסיק ש-
אינה ב-CO-RE.
ב.
נראה רדוקציה
ונסיק ש-
אינה
ב-RE.
א.
נגדיר את הפונקציה הבאה:
. פעולת
תוגדר באופן הבא:
לכל קלט
, המכונה תריץ ראשית את
על
. כאשר
עוצרת, היא תעבור למצב מקבל אם
הינו 1 או 11 או 100.
פונקציה זו הינה רדוקציה:
- פונקציה מלאה: לכל
ולכל
מוגדר פלט הפונקציה.
- פונקציה ניתנת לחישוב: ניתן לבנות מכונה שתריץ את
על
, וכן ניתן בפשטות להרכיב עליה מכונה שתקבל
עבור הקלטים המבוקשים.
- תקפות: נחלק
לשני מקרים:
א. אם
אינו שייך ל-HP, אזי
הינה מכונה שלא תעצור,
והשפה
המתאימה לה היא השפה הריקה, ומכאן
.
ב. אם
שייך ל-HP, אזי
היא מכונה שמקבלת עבור
אחד משלושת הקלטים 1,11,100. מתקיים כי
.
ניתן לראות כי אכן התקפות מתקיימת.
הראנו רדוקציה
ומכאן
אינה
ב-CO-RE.
ב.
נגדיר את הפונקציה הבאה:
.
פעולת
תוגדר באופן הבא: עבור קלט
: אם
או
או
אזי המכונה עוצרת ומקבלת. אחרת המכונה מריצה את
על
. כאשר
עוצרת, המכונה מקבלת את
.
נטען שפונקציה זו הינה רדוקציה:
- פונקציה מלאה: לכל
ולכל
מוגדר פלט הפונקציה.
- פונקציה ניתנת לחישוב: ניתן לממש פונקציה כזו על ידי פעולת קומפילציה פשוטה.
- תקפות:
לא נוכיח את התקפות באופן פורמלי, אך נביט בשפה המוגדרת על ידי
:
השפה
הינה
אם
. אחרת, השפה תהיה
.
הראנו רדוקציה
ומכאן
אינה
ב-RE.
החלק הראשון
בבקשה