תורת החישוביות/בעיות זיהוי ובעיות חיפוש: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
 
שורה 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> לפי [[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]] המורחב.