כריעות
ויקיפדיה האנציקלופדיה encyclopedia
בלוגיקה, בעיית הכרעה (בעיה שבה בהינתן קלט יש לתת תשובה של כן או לא) נקראת כריעה אם קיים אלגוריתם שקובע מה התשובה עבור קלט נתון. לדוגמה, בעיית ההכרעה "האם הקלט הוא מספר ראשוני?" היא כריעה, מכיוון שקיים אלגוריתם אשר מבדיל בין מספרים ראשוניים לבין מספרים פריקים. מערכת פורמלית נקראת כריעה אם ניתן להחליט האם כל טיעון הוא תקף. בעיות חשובות רבות אינן כריעות, כלומר, ניתן להוכיח שלא קיים אלגוריתם אשר עונה נכונה עליהן לכל קלט.