פרטי המסמך:

הועלה: סוג מסמך: מסמך אונליין מסמך אונליין
עמודים: 32 הורדות: 13891
נושאים שונים בתורת החישוביות. דגש מיוחד על מכונת טיורינג והנושאים הקשורים לה. הנושאים במסמך: בעיות לא פתירות, מכונות טיורינג, שקילות בין מודלים, מכונה אוניברסלית, בעיות הכרעה, רדוקציות וכן נציג גם שפות שאינן כריעות.

1. מבוא

1.1 בעיות לא פתירות והנושאים במסמך

בעיות לא פתירות:

  • בהינתן שתי תוכניות מחשב, האם הן שקולות? (בהינתן קלט זהה מפיקות פלט זהה)
  • בהנתן תוכניתM וקלט X, האם ניתן לבדוק האם M עוצרת על X.
  • בהנתן תוכניתM , האם ניתן לבדוק אם היא עוצרת לכל קלט?

הגדרה: תוצאות שליליות נסיבתיות הינו אוסף בעיות המקיים ש: או לכל הבעיות בקבוצה קיים פתרון יעיל, או שלאף אחת מהן אין פתרון כזה.

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

הנושאים בהם יעסוק מסמך זה:

במהלך קריאת המסמך קל ללכת לאיבוד בין המוני הפרטים, ולאבד את התמונה הגדולה – מה אנחנו מנסים להראות, לאן אנחנו הולכים. הנושאים בהם עוסק מסמך זה:

  • הצגת מכונת טיורינג כמודל חישוב כללי.
  • התזה של צ'רץ: כל מודל "סביר" ו-"כללי" של חישוב שקול למ"ט (נציג דוגמאות למספר מודלים ספציפיים).
  • נציג את נושא המכונה האוניברסילית.
  • מה ניתן לחשב על ידי מכונות טיורינג ומה לא ניתן לחשב.
  • הרדוקציה ושימושיה.

תגיות המסמך:

מאת: דנה

החלק הראשון

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

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

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

Microsoft VBScript runtime error '800a005e'

Invalid use of Null: 'Replace'

/document-details.asp, line 513