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