– בעיית החלטה P אמורה להיות ניתנת להכרעה למחצה (כלומר, יש לה אלגוריתם למחצה) אם השפה L של כל המופעים כן ל-P היא r.e. – (בעיית שקילות עבור DFA) בהינתן שני DFAs, האם הם מקבלים את אותה שפה? הוכחה: זכור את הטיעון של קנטור מההרצאה הראשונה.
כשאומרים שבעיה ניתנת להכרעה למחצה?
בעיות ניתנות להכרעה למחצה הן אלה של שמכונת טיורינג עוצרת על הקלט המקובל על ידה, אבל היא יכולה לעצור או לולאה לנצח על הקלט שנדחה על ידי מכונת הטיורינג. בעיות כאלה נקראות בעיות הניתנות לזיהוי טיורינג.
מהי בעיה הניתנת להכרעה חלקית?
הגדרה: אחת שהשפה המשויכת לה היא שפה נספירה רקורסיבית.באופן שווה, קיים אלגוריתם שעוצר ומוציא 1 עבור כל מופע שיש לו תשובה "כן", אבל במקרים שיש להם תשובה "לא" מותר לא לעצור או לעצור ולפלט 0.
האם בעיית עצירה ניתנת להכרעה חלקית?
אלן טיורינג הוכיח בשנת 1936 שאלגוריתם כללי הפועל על מכונת טיורינג שפותר את בעיית הבלימה עבור כל צמדי הקלט האפשריים של תוכנית לא יכול בהכרח להתקיים. לפיכך, בעיית ההפסקה אינה ניתנת להכרעה עבור מכונות טיורינג.
למה בעיית העצירה ניתנת להכרעה למחצה?
יש אומרים ששפה ניתנת להכרעה למחצה אם קיימת מכונת טיורינג ש עוצרת אם מילה שייכת לשפה (מקרים כן) ועשויה לדחות או להיכנס לאינסוף לולאה אם המילה לא שייכת לשפה (ללא מקרה).
