הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

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

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

4.2. המחלקה של שפת העצירה

טענה: שפת העצירה, HP, איננה שייכת ל-CO-RE.

הוכחה: ראשית נאמר כי שפת העצירה איננה שייכת ל-R. ניתן לראות זאת על ידי התרגיל המחשבתי הבא: נניח בשלילה ששפת העצירה כן שייכת ל-plot:$R$, אזי קיימת מכונה plot:${M_{HP}}$ המכריעה אותה. כלומר, בהינתן קידוד של מכונה וקלט, המכונה אומרת האם אותה מכונה עוצרת על הקלט או לא.

נגדיר מכונת טיורינג המתנהגת באופן הבא:

plot:$M'\left( w \right) = \left\{ {\begin{array}{*{20}{c}}    {{\text{if }}{{\text{f}}_{{{\text{M}}_{{\text{HP}}}}}}\left( {w,w} \right){\text{ accepts}}} \hfill & {{\text{infinite loop}}} \hfill  \\    {{\text{else}}} \hfill & {{\text{stop}}} \hfill  \\ \end{array} } \right.$

כעת נשאל, האם plot:$M'$ עוצרת כאשר היא מקבלת את הקידוד של עצמה, כלומר, האם plot:$M'\left( {M'} \right)$ עוצרת.



אם כן, אז לפי הפונקציה  שהגדרנו היא החזירה "לא", כלומר plot:$M'\left( {M'} \right)$ לא עוצרת.

אם היא לא עוצרת, plot:${{\text{f}}_{{{\text{M}}_{{\text{HP}}}}}}\left( {M',M'} \right)$ החזירה "כן", כלומר plot:$M'\left( {M'} \right)$ כן עוצרת.

קיבלנו סתירה ולכן לא קיימת מכונת טיורינג כנ"ל.

כעת אנחנו יודעים ש-HP לא שייכת ל-R. נראה כי היא שייכת ל-RE. ניתן לראות זאת על ידי בניית מכונה פשוטה M: המכונה מריצה את המכונה האוניברסלית עם המכונה והקלט הנתונים. אם היא עוצרת, המכונה מקבלת. מכונה זו אכן עומדת בדרישות: עבור כל זוג השייך ל-HP, לפי הגדרה המכונה האוניברסלית תעצור בסופו של דבר, ולכן M תעצור.

HP איננה שייכת ל-CO-RE. אם היא היתה שייכת ל-CO-RE הרי שהיא היתה גם שייכת לחיתוך בין CO-RE ל-RE, כלומר היא היתה שייכת ל-R, בסתירה לכך שראינו שהיא איננה ב-R.

תגיות המסמך:

לפרק הקודם4.1. דוגמאות לשפות במחלקות
לפרק הבא4.3. תרגיל חשוב
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד