תורת החישוביות/בעיות זיהוי ובעיות חיפוש: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירה |
זיהוי גורר חיפוש. חיפוש לא גורר זיהוי. |
||
שורה 7:
נאמר שהיחס S '''ניתן לזיהוי''' אם קיימת מ״ט שמקבלת את הקלט <math>(x,y)</math> אם הוא שייך ליחס S, ודוחה אחרת. זו היא בעצם בעיית ההכרעה של השפה
<center><math>L_S = \{ (x,y) \mid (x,y)\in S\}</math></center>
==הקשר בין חיפוש וזיהוי==
{{משפט|תוכן=
אם <math>L_S\in RE</math> אז היחס S ניתן לחיפוש{{רווח קשיח|4}}{{ש}}
(כלומר: '''זיהוי גורר חיפוש''')}}
הוכחה: אם <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^*\} \bigcup \{ (\langle M \ranlge, 1\mid \langle M \rangle \in L_{\emptyset} \</math></center>.
בעיית החיפוש ניתנת לפתרון בקלות: לכל קלט 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> לפי [[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]] המוכלל.
| |||