שפה נקראת Decidable או רקורסיבית אם יש מכונת טורינג שמקבלת ועוצרת בכל מחרוזת קלט w. כל שפה שניתן להחליט היא מקובלת על ידי טיורינג. בעיית החלטה P ניתנת להכרעה אם השפה L של כל המקרים כן ל-P ניתנת להכרעה.
למה אתה מתכוון ב-Decidability?
: יכול להחליט באופן ספציפי: מסוגל להחליט לפי או לא בעקבות האקסיומות של מערכת לוגית האם הלוגיקה הושלמה…? והאם היא ניתנת להכרעה, במובן זה שהייתה שיטה שהדגימה את האמת או השקר של כל אמירה? -
מה ההבדל בין ניתנות להכרעה ובלתי ניתנת להכרעה?
A בעיית החלטה ניתנת להכרעה אם קיים עבורה אלגוריתם החלטה. אחרת זה לא ניתן להכרעה. כדי להראות שבעיית החלטה ניתנת להכרעה, מספיק לתת לה אלגוריתם.
איך מחשבים את יכולת ההכרעה?
שפה ניתנת להכרעה אם ורק אם ניתן לזהות אותה והשלמה שלה. הוכחה. אם שפה ניתנת להכרעה, אזי ההשלמה שלה ניתנת להכרעה (על ידי סגירה תחת השלמה).
מהי בעיית ההכרעה?
(הגדרה) הגדרה: בעיית החלטה הניתנת לפתרון על ידי אלגוריתם שעוצר על כל הכניסות במספר סופי של שלבים השפה המשויכת נקראת שפה ניתנת להכרעה. ידוע גם כבעיה הניתנת להכרעה לחלוטין, ניתנת לפתרון אלגוריתמי, ניתנת לפתרון רקורסיבי.
