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