תורת החישוביות/בעיות זיהוי ובעיות חיפוש: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ויקיזציה |
|||
שורה 1:
{{תורת החישוביות}}
יהי <math>S\subseteq \Sigma^* \times \Sigma^*</math> יחס דו־מקומי
שורה 23 ⟵ 24:
בעיית החיפוש ניתנת לפתרון בקלות: לכל קלט 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> לפי [[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]] המורחב.
{{תורת החישוביות|מוגבל}}
[[קטגוריה:תורת החישוביות]]
| |||