תורת החישוביות/בעיות זיהוי ובעיות חיפוש: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←האם חיפוש גורר זיהוי?: הגהה |
|||
שורה 22:
להוכחת טענה זו נביט ביחס הבא:
<center><math>S = \{ (x,0) \mid x\in \Sigma^*\}\; \cup \;\{ (\langle M \rangle, 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> לפי [[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]] המורחב.
|