בעיית העצירה
בעיית העצירה שואלת: האם תוכנית תפסיק לרוץ על קלט מסוים? קלט הוא המידע שמכניסים לתוכנית. אלן טיורינג הראה ב-1936 שאין דרך כללית לבדוק את זה לכל תוכנית וקלט. מכונת טיורינג היא דגם רעיוני של מחשב. ההוכחה משתמשת ברעיון פשוט של סתירה. נניח שיש בודק Halt שמגיד אם תוכנית עוצרת על קלט. נבנה תוכנית A כך:...
התייחסות עצמית
התייחסות עצמית היא כשמשהו מדבר על עצמו. לפעמים רעיונות מדברים על עצמם. סמל כזה הוא הדרקון הבולע את זנבו. יש משפט שאומר "המשפט הזה הוא שקר". זה יוצר בעיה שנקראת פרדוקס. פרדוקס הוא מצב שנראה סותר. דקארט אמר: "אני חושב, משמע אני קיים". המחשבה על הספק מוכיחה שיש מישהו שחושב. יש טיעון שאומר: אם אלוהי...
תורת הרקורסיה
תורת הרקורסיה בודקת מה מחשבים יכולים לחשב ומה לא. היא עוסקת בפונקציות שמקבלות מספר ומחזירות מספר. מכונת טיורינג היא מכונה דמיונית שעוברת על הוראות פשוטות. כל מכונה כזו אפשר למספר במספר טבעי. יש מכונות שמפסיקות ומחזירות מספר. יש כאלו שאף פעם לא עוצרות. לכן לפעמים פונקציה לא מוגדרת על כל הקלטים. אור...
אורקל (מדעי המחשב)
אורקל הוא קופסה שחורה שנותנת תשובות לשאלה בודדת בצעד אחד. קופסה שחורה הוא דבר שאפשר לשאול אבל לא לראות איך הוא עובד. אורקלים יכולים לפתור בעיות מאוד קשות, אפילו בעיות שלא תמיד אפשר לחשב, כמו בעיית העצירה (שאלה אם תוכנה תפסיק או תרוץ לנצח). מכונת טיורינג היא דרך לתאר מחשב פשוט בתור מודל. מכונת טיורי...
מכונת טיורינג
מכונת טיורינג היא רעיון שמסביר איך מחשב עובד בפשטות. אלן טיורינג המציא את הרעיון ב-1936. דמיין סרט ארוך מאוד עם תאים עליו. על הסרט זז ראש קטן. הראש קורא את התא, יכול לכתוב בו ולנוע ימינה או שמאלה. על הסרט יש קלט, וזהו המידע שהמכונה מקבלת. הראש קורא ומחליט מה לכתוב ואיפה לזוז לפי כללים פשוטים. ...
אימות תוכנה
אימות תוכנה בודק שהמחשב עושה בדיוק את מה שאומרים לו. בדיקה רגילה בוחרת דוגמאות ובודקת אותן. זה טוב אבל לא בודק כל מצב. אימות מנסה להראות שזו עובדה נכונה בכל המקרים. שיטה אחת בונה "מודל" פשוט של התוכנית. מודל מתמטי הוא תיאור מתמטי של המערכת. המודל צריך להיות סופי, כלומר עם מספר מצבים שניתן לספור. ...
משפט רייס
משפט רייס אומר שאי אפשר לכתוב תוכנית שתבדוק תכונות "מעניינות" של מה שתוכנית אחרת מחשבת. "מעניינות" כאן פירושו תכונה שמופיעה בחלק מהפונקציות, אבל לא בכולן. יש הוכחה שמראה שזה בלתי אפשרי. משתמשים ברעיון של פונקציה ריקה. פונקציה ריקה היא פונקציה שלא מחזירה שום דבר כי התוכנית שלה לא עוצרת. נניח שיש...
הבונה העסוק
בונה העסוק שואלת שאלה פשוטה: כמה עבודה יכולה מכונת טיורינג לעשות לפני שהיא עוצרת. מכונת טיורינג זה מחשב תיאורטי. זהו מכשיר עם סרט ארוך וראש קורא. המכונה קוראת ומושכת את הסרט. היא פועלת לפי טבלת הוראות. יש לה מצבים פנימיים. לפעמים המכונה לעולם לא עוצרת. S(n) אומרת את מספר הצעדים הכי גדול שמכונה עם ...
בעיית הכרעה
בעיית הכרעה היא שאלה שיש לה תשובה של כן או לא. דוגמה פשוטה: האם מספר טבעי הוא ראשוני? זו בעיית הכרעה. למצוא מספר ראשוני עם 77 ספרות זו לא בעיית הכרעה. יש בעיות מפורסמות, כמו הבעיה העשירית של הילברט. אפשר לחשוב על בעיות הכרעה כמו רשימות של מילים ששייכות ל"שפה פורמלית" (שפה פורמלית = קבוצה של מילים ...
רדוקציה חישובית
רדוקציה היא דרך להחליף בעיה בבעיה אחרת שעוזרת לפתור אותה. לדוגמה, כדי למצוא את המספר הקטן ביותר בסדרה, אפשר למיין את המספרים ואז לקחת את הראשון. רדוקציה עוזרת להראות אם בעיה ניתנת לפתרון או לא. משתמשים בה כדי לקשר בעיות שקשה לפתור. רדוקציה פולינומית היא רדוקציה שחישוב שלה יעיל. אם יש פתרון יעיל לב...