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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ ויקיזציה
Gran (שיחה | תרומות)
שורה 11:
 
==הקשר בין חיפוש וזיהוי==
===זיהוי גורר חיפוש===
{{משפט|תוכן=
אם <math>L_S\in RE</math> אז היחס S ניתן לחיפוש{{רווח קשיח|4}}{{ש}}
שורה 17 ⟵ 18:
{{תזכורת|שיטת ההרצה המבוקרת הוצגה בפרק [[תורת החישוביות/מודל לבעיות הכרעה]]}}
{{-}}
<u>===האם זיהויחיפוש גורר חיפושזיהוי?</u>===
:התשובה היא '''לא!'''. ייתכן שלכל x קיימים מספר ערכי y, אחד מהם קל למצוא (ומ״ט של החיפוש תחזיר אותו שוב ושוב), ולאו דווקא נוכל למצוא את ערך ה־y שניתן כקלט.
 
להוכחת טענה זו נביט ביחס הבא: