כדי להראות ששפה ניתנת להכרעה, אנחנו צריכים ליצור מכונת טיורינג שתעצור בכל מחרוזת קלט מהאלפבית של השפה. מכיוון ש-M הוא DFA, כבר יש לנו את מכונת הטיורינג ורק צריכים להראות שה-DFA נעצר בכל קלט.
איך מחשבים את יכולת ההכרעה?
שפה ניתנת להכרעה אם ורק אם ניתן לזהות אותה והשלמה שלה. הוכחה. אם שפה ניתנת להכרעה, אזי ההשלמה שלה ניתנת להכרעה (על ידי סגירה תחת השלמה).
איך מוכיחים את יכולת ההחלטה של טיורינג?
הוכח שהשפה שהיא מזהה שווה לשפה הנתונה ושהאלגוריתם עוצר בכל הקלט. כדי להוכיח ששפה נתונה ניתנת לזיהוי טיורינג: בנה אלגוריתם שמקבל בדיוק את המחרוזות שנמצאות בשפהזה חייב לדחות או ללולאה על כל מחרוזת שאינה בשפה.
איך אתה יודע אם שפה ניתנת לזיהוי?
שפה L ניתנת לזיהוי אם ורק אם קיים מאמת עבור L, כאשר המאמת הוא מכונת טיורינג שעוצרת בכל הכניסות ולכל w∈Σ∗, w∈L↔∃c∈Σ∗. V מקבל ⟨w, c⟩.
איך אתה מראה שבעיה לא ניתנת להכרעה?
בעיית הטוטאליות אינה ניתנת להכרעה
בעיית העצירה יכולה לשמש כדי להראות שבעיות אחרות אינן ניתנות להכרעה. בעיית טוטליות: פונקציה (או תוכנית) F אמורה להיות כוללת אם F(x) מוגדר עבור כל x (או באופן דומה, אם F(x) נעצר עבור כל x). לא ניתן להחליט אם פונקציה F היא טוטאלית או לא.
