תורת החישוביות/בעיות זיהוי ובעיות חיפוש: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
זיהוי גורר חיפוש. חיפוש לא גורר זיהוי. |
|||
שורה 15:
הוכחה: אם <math>L_S\in RE</math> אז קיימת מ״ט שמקבלת את <math>L_S</math>, שנסמנה ב־<math>M</math>. בהנתן קלט x נמצא בעזרת הרצה מבוקרת של M ערך y כך ש־<math>(x,y)\in S</math> אם אין ערך y כנ״ל, המכונה לא תעצור.
{{תזכורת|שיטת ההרצה המבוקרת הוצגה בפרק [[תורת החישוביות/מודל לבעיות הכרעה]]}}
{{-}}
<u>האם זיהוי גורר חיפוש?</u>
:התשובה היא '''לא!'''. ייתכן שלכל x קיימים מספר ערכי y, אחד מהם קל למצוא (ומ״ט של החיפוש תחזיר אותו שוב ושוב), ולאו דווקא נוכל למצוא את ערך ה־y שניתן כקלט.
להוכחת טענה זו נביט ביחס הבא:
<center><math>S = \{ (x,0) \mid x\in \Sigma^*\}\; \
בעיית החיפוש ניתנת לפתרון בקלות: לכל קלט x נוציא כפלט את המחרוזת "0". לעומת זאת, בעיית הזיהוי, עבור קלט מהצורה <math>(x,1)</math>
הוא בלתי־אפשרי. פורמלית, ניתן להראות שהשפה <math>L_S \notin RE</math> ע״י הרדוקציה <math>L_\emptyset \le L_S</math>, והידיעה ש־<math>L_\emptyset \notin RE</math> לפי [[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]]
| |||