הצגת המקור של הדף "כריעות"

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

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

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

== שפות שאינן כריעות ==
קל להוכיח כי קיימות בעיות שלא ניתן לכתוב אלגוריתם לפתרונן, וכך למעשה, השפות המתאימות אינן כריעות. עובדה זו נובעת משיקולי [[מנייה|ספירה]]: אנחנו יכולים ליצור רק <math>\aleph_0</math> ([[אלף אפס|אָלֶף אֶפֶס]]) מכונות טיורינג ואילו יש <math>\aleph</math> (אלף – [[עוצמת הרצף]]) שפות. 
<!-- ישנן <math>\!\, \aleph</math> שפות כי שפה היא קבוצה של מילים. קבוצת המילים מעל א"ב כלשהו, למשל {0,1} היא בעלת עוצמה <math>\!\, \aleph_0</math>. לכן, כל שפה היא למעשה תת-קבוצה של קבוצת כל המילים. לכן, היא איבר ב[[קבוצת החזקה]] של קבוצת המילים. מכאן כי יש 2 בחזקת <math>\!\, \aleph_0</math> שפות שכאלה. דהיינו, <math>\!\, \aleph</math>. -->

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

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

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

ה[[חיתוך (מתמטיקה)|חיתוך]] של שתי המחלקות לעיל מהווה את המחלקה <math>R</math>. מאידך, ישנן גם בעיות שהן ב-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}}, [http://www.ams.org/mathscinet-getitem?mr=1464942|MR 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}}

{{בקרת זהויות}}

[[קטגוריה:כריעות|*]]
[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:חישוביות]]