בעיות שאינן פתירות
הוצג| English | משמעות |
|---|---|
| cannot/ˈkænɒt/ | אינו יכול |
| decidable/dɪˈsaɪdəbl/ | ניתן להכרעה |
| undecidable/ˌʌndɪˈsaɪdəbl/ | בלתי ניתן להכרעה |
| limit/ˈlɪmɪt/ | גבול |
| inefficient/ɪnɪˈfɪʃənt/ | בלתי יעיל |
לא כל בעיה ניתנת לפתרון
- לא כל בעיה ניתנת לפתרון על ידי מחשב, אף בעיקרון.
- כדי להבין למה, נסווג את הבעיות לשני סוגים.
- סוג אחד שבו המחשב תמיד יכול לתת מענה; השני הוא שאינו יכול.
- זוהי עובת דבר מוכחת במדעי המחשב, ולא פערה שעשויה להתמלא בעתיד.
בעיה פתירה היא אחת שבה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
"האם n זוגי?" היא בעיה פתורה – ניתן לתת עליה תשובה תמיד.
בעיות החלטיות
- בעיה החלטית היא בעלת אלגוריתם שמספק תמיד תשובה נכונה כן/לא לכל מקרה.
- "האם מספר זה זוגי?" היא בעיה החלטית — מבחן פשוט תמיד נותן תשובה נכונה.
- "האם מספר זה ראשוני?" גם היא החלטית, גם אם האלגוריתם איטי למספרים ענקיים.
- אם קיים אלגוריתם תקני לכל המקרים, הבעיה היא החלטית.
פתירה או בלתי פתירה?
בעיה פתירה היא בעלת אלגוריתם שעונה תמיד נכון לכל מקרה; בעיה בלתי פתירה אין לה אלגוריתם כזה — זהו דבר בלתי אפשרי, ולא רק איטי.
בעיה בלתי-פתירה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חלק מהמקרים מנעלים את כל התוכניות האפשריות.
קביעה כללית על כך אם תוכנית נתונה תפסיק לעבוד לעולם היא:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אין אלגוריתם יחיד שמשיב נכון עבור כל תוכנית.
בלתי-פתירות מסמנת מחסום קשה ______ על מה חישוב יכול להשיג.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חלק משאלות אין להן אלגוריתם כללי.
בעיות בלתי החלטיות
- בעיה בלתי החלטית היא שאין לה אלגוריתם שפתור כל מקרה בצורה נכונה.
- ללא תודה כמה שתהיה התוכנית חכמה, ישנם מקרים שהיא לא תצליח לפתור.
- הדוגמה הקלאסית: החלטה כללית, האם תוכנית נתונה כלשהי תפסיק לעבוד לעולם.
- בלתי החלטיות היא גבול של מה שחישוב יכול להשיג — ישנן שאלות שאין להן אלגוריתם כללי.
בלתי-פתירות ואי-יעילות (איטיות) הם אותו דבר.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אי-יעילות ניתנת לפתרון באיטיות; בלתי-פתירות לא ניתנת לפתרון בכל המקרים כלל.
בדיקה אם מספר הוא ראשוני היא בעיה פתורה, גם אם היא איטית למספרים ענקיים.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אלגוריתם תמיד נותן תשובה; איטיות אינה זהה לחוסר אפשרות.
בלתי החלטיות אינה רק איטיות
- אל תבלבו בין בלתי פתיר לבין לא יעיל.
- בעיה לא יעילה יכולה להיות פתורה, רק לאט. בעיה בלתי פתירה אינה יכולה להיות פתורה בכל המקרים כלל.
מספר ראשוני מול עצירת תוכנית. בדיקה האם מספר הוא ראשונית היא בעיה פתירה — אלגוריתם תמיד נותן מענה, גם אם איטי למספרים ענקיים. אך קביעה כללית האם כל תוכנית תיעצר היא בלתי פתירה: אין אלגוריתם אחד שינבא נכון לכל תוכנית. איטיות אינה שווה לחוסר אפשרות.
בעיה פתירה יש לה אלגוריתם שתמיד נותן מענה נכון ("האם n זוגי?", "האם n ראשוני?"). בעיה בלתי פתירה אין לה אלו אלגוריתם כזה לכל המקרים (האם תוכנית תיעצר?) — זהו גבול אמיתי של חישוב. בלתי פתיר אומר שזה לא ניתן לפתור כלל, ולא רק לא יעיל (איטי).