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

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

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

2.2. שיטת ההוכחה של שקילות

השיטה: בהנתן מ"ט M ממודל A, נבנה מ"ט plot:\[M'\] ממודל B המחשבת את אותה הפונקציה, ולהיפך.

הערות:

  • אסור להסתמך בבעיה על תכונות ספציפיות של M. הבנייה צריכה להיות כללית לכל M מהמודל.
  • קיימים מודלים חזקים יותר מהמודל הסטנדרטי של מ"ט וקיימים מודלים חלשים יותר.
  • בד"כ הבניה שנבנה תממש סימולציה צעד אחד צעד.
  • דגש חשוב: אנחנו בודקים האם המודלים מקבלים את אותה קבוצת שפות. אנחנו לא בודקים האם קבוצת המכונות שקיימות בקבוצה אחת שווה לקבוצת המכונות שבקבוצה השניה.

תגיות המסמך:

לפרק הקודם2.1. דוגמאות
לפרק הבא2.2.1. תרגיל
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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