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

1. מבוא

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

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

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

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

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

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

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

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