כריעות

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

הגדרה פורמלית

באופן פורמלי, שפה $L$ תיקרא כריעה אם קיימת מכונת טיורינג $M$ אשר עוצרת על כל קלט ומקבלת בדיוק את השפה $L$. במילים אחרות, אם מכונת טיורינג $M$ תקבל כקלט מילה בשפה, היא תעצור ב"מצב מקבל", ואם הקלט הוא מילה שאינה בשפה $L$, המכונה תעצור ב"מצב לא מקבל" (או "מצב דחייה"). את מחלקת הבעיות (השפות) הכריעות מסמנים ב-$R$.

שפות שאינן כריעות

קל להוכיח כי קיימות בעיות שלא ניתן לכתוב אלגוריתם לפתרונן, וכך למעשה, השפות המתאימות אינן כריעות. עובדה זו נובעת משיקולי ספירה: אנחנו יכולים ליצור רק $\aleph _{0}$ (אָלֶף אֶפֶס) מכונות טיורינג ואילו יש $\aleph$ (אלף – עוצמת הרצף) שפות.

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

שפות כריעות-למחצה

קיימות שפות שהן כריעות-למחצה (חיוביות), כלומר, קיימת מכונה אשר עוצרת ומזהה כל קלט ששייך לשפה, אבל עשויה שלא לעצור לעולם אם הקלט אינו בשפה. הקבוצה המכילה את כלל השפות הללו מסומנת בתור המחלקה RE.

בצורה מקבילה מגדירים את מחלקת השפות co-RE להיות קבוצת כל השפות $L$ עבורן קיימת מכונת טיורינג אשר עוצרת ודוחה עבור כל מילת קלט שאינה בשפה $L$, אבל ייתכן שאינה עוצרת עבור מילים השייכות לשפה $L$.

החיתוך של שתי המחלקות לעיל מהווה את המחלקה $R$. מאידך, ישנן גם בעיות שהן ב-RE אך לא ב-co-RE ולהפך, למשל, בעיית העצירה.

לעומת זאת, ישנן שפות שהן לא ב-RE וגם לא ב-co-RE. כך למשל בעיית העצירה המוכללת, ששואלת בהינתן כקלט מכונת טיורינג, אם המכונה עוצרת על כל הקלטים האפשריים. כמו כן, השפה המכילה את כל מכונות טיורינג שהשפות שלהן רגולריות, והשפה המכילה את כל מכונות טיורינג שהשפות שלהן חסרות הקשר, שתיהן לא ב- RE ולא ב- co-RE (ובפרט אינן כריעות).

לקריאה נוספת

• Chagrov, Alexander; Zakharyaschev, Michael (1997), Modal logic, Oxford Logic Guides, 35, The Clarendon Press Oxford University Press, ISBN 978-0-19-853779-3, 1464942
• Davis, Martin (1958), Computability and Unsolvability, McGraw-Hill Book Company, Inc, New York
• Enderton, Herbert (2001), A Mathematical Introduction to Logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3

• M. Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997.
• J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., 1979

קישורים חיצוניים

• כריעות, באתר MathWorld (באנגלית)