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

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

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

4.3. תרגיל חשוב

תרגיל: הוכח כי השפה הבאה הינה ב-RE:

plot:$L = \left\{ {\left\langle M \right\rangle |L\left( M \right) \ne \phi } \right\}$

חשיבות התרגיל הינה בשיטת הפתרון, החוזרת על עצמה בתרגילים רבים.

פתרון: נראה כי השפה הינה ב-RE על ידי בניית מכונה plot:$M'$ המקבלת אותה.

המכונה plot:$M'$:

באיטרציה ה-plot:$i$ של המכונה, היא:

  • מוסיפה על הסרט את המחרוזת ה-plot:$i$ בסדר הלקסיקוגרפי של plot:${\Sigma ^*}$.
  • לכל קלט שכבר כתוב על המכונה, היא מפעילה עליו את plot:$M$ עוד plot:$i$ צעדים.
  • אם אחד הקלטים מגיע למצב מקבל – נעצור ונקבל.

חשוב לציין: במידה וקיים קלט עבורו M עוצרת – נגיע אליו בזמן סופי (על ידי מניה על כל הקלטים מובטח שנגיע לכל קלט סופי שהמכונה מקבלת). בנוסף, כל איטרציה של plot:$M'$ מורכבת ממספר סופי של צעדים.



תגיות המסמך:

לפרק הקודם4.2. המחלקה של שפת העצירה
לפרק הבא5. רדוקציות
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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