Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
בלוגיקה, בעיית הכרעה (בעיה שבה בהינתן קלט יש לתת תשובה של כן או לא) נקראת כריעה אם קיים אלגוריתם שקובע מה התשובה עבור קלט נתון. לדוגמה, בעיית ההכרעה "האם הקלט הוא מספר ראשוני?" היא כריעה, מכיוון שקיים אלגוריתם אשר מבדיל בין מספרים ראשוניים לבין מספרים פריקים. מערכת פורמלית נקראת כריעה אם ניתן להחליט האם כל טיעון הוא תקף. בעיות חשובות רבות אינן כריעות, כלומר, ניתן להוכיח שלא קיים אלגוריתם אשר עונה נכונה עליהן לכל קלט.
באופן פורמלי, שפה תיקרא כריעה אם קיימת מכונת טיורינג אשר עוצרת על כל קלט ומקבלת בדיוק את השפה . במילים אחרות, אם מכונת טיורינג תקבל כקלט מילה בשפה, היא תעצור ב"מצב מקבל", ואם הקלט הוא מילה שאינה בשפה , המכונה תעצור ב"מצב לא מקבל" (או "מצב דחייה"). את מחלקת הבעיות (השפות) הכריעות מסמנים ב-.
קל להוכיח כי קיימות בעיות שלא ניתן לכתוב אלגוריתם לפתרונן, וכך למעשה, השפות המתאימות אינן כריעות. עובדה זו נובעת משיקולי ספירה: אנחנו יכולים ליצור רק (אָלֶף אֶפֶס) מכונות טיורינג ואילו יש (אלף – עוצמת הרצף) שפות.
את שאלת קיומן של שפות "מעניינות" (זאת אומרת, ניתנות לתיאור סופי) שאינן כריעות, פתר אלן טיורינג כאשר הוכיח כי בעיית העצירה אינה כריעה. משפט רייס הרחיק לכת והוכיח כי למעשה כל בעיה ששואלת שאלה לא טריוויאלית על אודות השפה של מכונת טיורינג, אינה כריעה.
קיימות שפות שהן כריעות-למחצה (חיוביות), כלומר, קיימת מכונה אשר עוצרת ומזהה כל קלט ששייך לשפה, אבל עשויה שלא לעצור לעולם אם הקלט אינו בשפה. הקבוצה המכילה את כלל השפות הללו מסומנת בתור המחלקה RE.
בצורה מקבילה מגדירים את מחלקת השפות co-RE להיות קבוצת כל השפות עבורן קיימת מכונת טיורינג אשר עוצרת ודוחה עבור כל מילת קלט שאינה בשפה , אבל ייתכן שאינה עוצרת עבור מילים השייכות לשפה .
החיתוך של שתי המחלקות לעיל מהווה את המחלקה . מאידך, ישנן גם בעיות שהן ב-RE אך לא ב-co-RE ולהפך, למשל, בעיית העצירה.
לעומת זאת, ישנן שפות שהן לא ב-RE וגם לא ב-co-RE. כך למשל בעיית העצירה המוכללת, ששואלת בהינתן כקלט מכונת טיורינג, אם המכונה עוצרת על כל הקלטים האפשריים. כמו כן, השפה המכילה את כל מכונות טיורינג שהשפות שלהן רגולריות, והשפה המכילה את כל מכונות טיורינג שהשפות שלהן חסרות הקשר, שתיהן לא ב- RE ולא ב- co-RE (ובפרט אינן כריעות).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.