הצגת המקור של הדף "RE (מחלקת סיבוכיות)"

ב[[חישוביות|תורת החישוביות]] וה[[סיבוכיות]], המחלקה '''RE''' (מ[[אנגלית]]: '''Recursively Enumerable''') היא [[מחלקת סיבוכיות|מחלקה]] אשר מכילה את כל [[בעיית הכרעה|בעיות ההכרעה]] שעל התשובה "כן" קיימת [[מכונת טיורינג]] היכולה לוודא זאת בזמן סופי. באופן לא פורמלי, הכוונה שאם התשובה לבעיה נתונה היא "כן", אזי קיים תהליך כלשהו שיכול לוודא זאת בזמן סופי, ותהליך זה לעולם לא יפלוט "כן" אם התשובה האמיתית היא "לא". אף על פי כן, אם התשובה האמיתית היא "לא", התהליך לא מחויב לעצור ואף יכול להיכנס ללולאה אינסופית בחלק מהמקרים. תהליך כזה נקרא לעיתים דמוי-אלגוריתם או אלגוריתם למחצה, על מנת להבדיל מ[[אלגוריתם]] אשר נועד לחשב תשובה עבור בעיית הכרעה.

באופן דומה, ניתן להגדיר את המחלקה המשלימה, '''coRE''', בתור מחלקת כלל השפות הפורמליות שהמשלימה שלהן נמצאת ב-'''RE''', דהי, המחלקה מכילה את כלל השפות הפורמליות שניתן לשלול שייכות בזמן סופי, אך הוכחת שייכות יכולה לקחת זמן אינסופי.

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

על מנת להראות שקילות זו, נשים לב שאם קיימת מכונה <math>E</math> כך שהיא מונה את כל הקלטים שמתקבלים, מכונה אחרת שמקבלת מחרוזת כקלט יכולה להריץ את <math>E</math> ולקבל (כלומר לענות כן) אם המחרוזת ניתנת למנייה. באופן הפוך, אם מכונה <math>M</math> מקבלת (עונה כן) כאשר הקלט הוא [[שפה פורמלית]], מכונה אחרת יכולה למנות את כל המחרוזות שנמצאות בשפה על ידי הרצת <math>M</math> באיטרציות על כל קלט ולפלוט את כל הפלטים ש-<math>M</math> מקבלת.

== יחסים בין המחלקה למחלקות אחרות ==
מחלקת ה[[שפה רקורסיבית|שפות הרקורסיביות]] ('''[[R (מחלקת סיבוכיות)|R]]''') היא [[תת-קבוצה]] של '''RE''' ו-'''coRE''' ולמעשה, R מהווה את החיתוך בין שתי המחלקות, שכן אנו יכולים ל[[כריעות|הכריע]] כל בעיה שקיימת לה מכונת טיורינג המקבלת אותה וקיימת לה מכונת טיורינג הדוחה אותה על ידי הרצה לסירוגין של שתי המכונות עד שאחת מהן עוצרת ופולטת תשובה. לכן:
:<math>\mbox{R} = \mbox{RE}\cap\mbox{coRE}</math>.

באופן הפוך, הקבוצה של כלל השפות הפורמליות שאינן ב-RE ואינן ב-coRE נקראת '''NRNC'''. זוהי מחלקת כלל השפות הפורמליות שלא קיימת להן מכונת טיורינג היכולה להוכיח או להפריך שייכות אליהן בזמן סופי, כלומר:
:<math>\mbox{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{coRE})</math>.

לא רק שבעיות כאלו אינן כריעות, גם הן וגם המשלימות שלהן אינן ניתנות למנייה רקורסיבית.

== בעיות שלמות ב-RE ==
המחלקה '''RE-Complete''' היא תת-קבוצה של המחלקה '''RE''' המכילה את כל בעיות ההכרעה שהן שלמות ב-RE. ניתן לומר כי הן הבעיות "הכי" קשות הניתנות למנייה רקורסיבית. באופן כללי, אין הגבלות על ה[[רדוקציה חישובית|רדוקציות]] פרט לכך שהן אמורות להיות פונקציות מלאות המוגדרות לכל קלט ותקפות.

דוגמאות לבעיות שהן שלמות ב-RE:
# [[בעיית העצירה]]: בהינתן [[תוכנית מחשב]] ו[[קלט]], האם התוכנית תסיים את פעולתה בשלב כלשהו עבור קלט זה.
# [[משפט רייס]] אומר כי הכרעה של שייכות עבור כל תת-קבוצה לא טרוויאלית של קבוצת [[פונקציה בת-חישוב|פונקציות רקורסיביות]] היא RE-קשה. היא תהיה שלמה אם הקבוצה היא ניתנת למנייה רקורסיבית.
# [[ג'ון מייהיל]] {{אנ|John Myhill}} ([[1955]]) הוכיח כי כל ה[[קבוצה יצירתית|קבוצות היצירתיות]] {{אנ|Creative and productive sets}} הן RE-שלמות.
# [[בעיית המילה]] {{אנ|Word problem (mathematics)}} היוניפורמית עבור [[חבורה (מבנה אלגברי)|חבורות]] ו[[חבורה למחצה|חבורות למחצה]].
# קביעת שייכות עבור [[דקדוק בלתי-מוגבל]] {{אנ|Unrestricted grammar}} כללי (טיפוס 0 ב[[היררכיית חומסקי]]).
# בעיית ה[[תקפות (לוגיקה)|תקפות]] עבור [[שפה מסדר ראשון|תחשיב פרדיקטים מסדר ראשון]].
# [[בעיית ההתאמה של פוסט]]
# קביעה אם ל[[משוואה דיופנטית]] יש פתרונות ב[[מספר שלם|שלמים]].

== בעיות שלמות ב-coRE ==
המחלקה '''coRE-Complete''' היא תת-קבוצה של המחלקה '''coRE''' המכילה את כל בעיות ההכרעה שהן שלמות ב-coRE.

דוגמאות לבעיות שהן שלמות ב-coRE:
# [[בעיית הדומינו]] ב[[אריחי ואנג]].
# בעיית ה[[ספיקות]] {{אנ|Satisfiability}} עבור [[שפה מסדר ראשון|תחשיב פרדיקטים מסדר ראשון]].

== קישורים חיצוניים ==
* {{קישור כללי|כתובת=https://complexityzoo.net/Complexity_Zoo:R#re|הכותב=[[סקוט אהרונסון]]|כותרת=Class RE|אתר=באתר Complexity Zoo|שפה=אנגלית}}
* {{קישור כללי|כתובת=https://complexityzoo.net/Complexity_Zoo:C#core|הכותב=[[סקוט אהרונסון]]|כותרת=Class coRE|אתר=באתר Complexity Zoo|שפה=אנגלית}}

{{מחלקות סיבוכיות}}
[[קטגוריה:מחלקות סיבוכיות]]