תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

8. בעיות חיפוש

הגדרה: בהינתן יחס דו מקומי $plot:$S \subseteq {\Sigma ^*} \times {\Sigma ^*}$$ אומרים שמכונת טיורינג plot:$M$ פותרת את בעיית החיפוש של plot:$S$ אם לכל plot:$x$ : אם קיים plot:$y$ כך ש- $plot:$\left( {x,y} \right) \in S$$ , אז עוצרת עם כזה כפלט. אם לא קיים כנ"ל, אז לא עוצרת.

נשים לב שקיימת התאמה בין יחס לשפה. $plot:${L_S} = \left\{ {\left( {x,y} \right)|\left( {x,y} \right) \in S} \right\}$$ .

בעיית הזיהוי של $plot:$ \equiv S$$ בעיית הזיהוי של $plot:${L_s}$$ , כלומר התשובה לשאלה האם $plot:${L_s} \in RE$$ .

לכל יחס plot:$S$ מתקיים כי זיהוי $plot:$ \Leftarrow $$ חיפוש אולם חיפוש זיהוי.

חיפוש: בהינתן plot:$x$ מצא plot:$y$ מתאים. זיהוי: נתונים $plot:$\left( {x,y} \right)$$ , האם הם שייכים ליחס plot:$S$ ?

נביא דוגמא לצורך המחשת ההבדל בין חיפוש לזיהוי:

יהי plot:$S$ היחס הבא: $plot:$S = \left\{ {\left( {\left\langle {{M_1}} \right\rangle ,\left\langle {{M_2}} \right\rangle } \right)|L\left( {{M_1}} \right) = L\left( {{M_2}} \right)} \right\}$$ .

בעיית הזיהוי במקרה זה היא בעצם למצוא מכונה המקבלת את $plot:${L_{EQ}}$$ , אבל כפי שכבר ראינו, $plot:${L_{EQ}} \notin RE$$ .

לעומת זו, בעית חיפוש במקרה זה היא קלה: בהינתן מכונה $plot:${M_1}$$ , נוכל בקלות למצוא $plot:${M_2}$$ שמתאים לה – נשכפל פשוט את $plot:${M_1}$$ , וברור שהמכונה המשוכפלת תהיה בעלת אותה שפה.