https://www.yisraelpedia.com/index.php?action=history&feed=atom&title=RE_%28%D7%9E%D7%97%D7%9C%D7%A7%D7%AA_%D7%A1%D7%99%D7%91%D7%95%D7%9B%D7%99%D7%95%D7%AA%29 2026-09-15T07:28:05Z היסטוריית הגרסאות של הדף הזה בוויקי MediaWiki 1.43.8 https://www.yisraelpedia.com/index.php?title=RE_(%D7%9E%D7%97%D7%9C%D7%A7%D7%AA_%D7%A1%D7%99%D7%91%D7%95%D7%9B%D7%99%D7%95%D7%AA)&diff=913115&oldid=prev 2025-05-04T22:03:31Z

<p>הגהה, איבר זה זכר ומכאן &#039;הוא&#039;</p> <p><b>דף חדש</b></p><div>ב[[חישוביות|תורת החישוביות]] וה[[סיבוכיות]], המחלקה &#039;&#039;&#039;RE&#039;&#039;&#039; (מ[[אנגלית]]: &#039;&#039;&#039;Recursively Enumerable&#039;&#039;&#039;) היא [[מחלקת סיבוכיות|מחלקה]] אשר מכילה את כל [[בעיית הכרעה|בעיות ההכרעה]] שעל התשובה &quot;כן&quot; קיימת [[מכונת טיורינג]] היכולה לוודא זאת בזמן סופי. באופן לא פורמלי, הכוונה שאם התשובה לבעיה נתונה היא &quot;כן&quot;, אזי קיים תהליך כלשהו שיכול לוודא זאת בזמן סופי, ותהליך זה לעולם לא יפלוט &quot;כן&quot; אם התשובה האמיתית היא &quot;לא&quot;. אף על פי כן, אם התשובה האמיתית היא &quot;לא&quot;, התהליך לא מחויב לעצור ואף יכול להיכנס ללולאה אינסופית בחלק מהמקרים. תהליך כזה נקרא לעיתים דמוי-אלגוריתם או אלגוריתם למחצה, על מנת להבדיל מ[[אלגוריתם]] אשר נועד לחשב תשובה עבור בעיית הכרעה.<br /> <br /> באופן דומה, ניתן להגדיר את המחלקה המשלימה, &#039;&#039;&#039;coRE&#039;&#039;&#039;, בתור מחלקת כלל השפות הפורמליות שהמשלימה שלהן נמצאת ב-&#039;&#039;&#039;RE&#039;&#039;&#039;, דהי, המחלקה מכילה את כלל השפות הפורמליות שניתן לשלול שייכות בזמן סופי, אך הוכחת שייכות יכולה לקחת זמן אינסופי.<br /> <br /> == הגדרה שקולה ==<br /> באופן שקול, ניתן להגדיר את המחלקה &#039;&#039;&#039;RE&#039;&#039;&#039; בתור מחלקת כלל בעיות ההכרעה כך שקיימת מכונת טיורינג היכולה למנות את כל מופעי ה-&quot;כן&quot;, זו אחר זו (מכאן המשמעות של &quot;ניתנת למנייה&quot;). כל איבר במחלקה הוא [[קבוצה ניתנת למנייה רקורסיבית]] ולכן מהווה קבוצה דיופנטית.<br /> <br /> על מנת להראות שקילות זו, נשים לב שאם קיימת מכונה &lt;math&gt;E&lt;/math&gt; כך שהיא מונה את כל הקלטים שמתקבלים, מכונה אחרת שמקבלת מחרוזת כקלט יכולה להריץ את &lt;math&gt;E&lt;/math&gt; ולקבל (כלומר לענות כן) אם המחרוזת ניתנת למנייה. באופן הפוך, אם מכונה &lt;math&gt;M&lt;/math&gt; מקבלת (עונה כן) כאשר הקלט הוא [[שפה פורמלית]], מכונה אחרת יכולה למנות את כל המחרוזות שנמצאות בשפה על ידי הרצת &lt;math&gt;M&lt;/math&gt; באיטרציות על כל קלט ולפלוט את כל הפלטים ש-&lt;math&gt;M&lt;/math&gt; מקבלת.<br /> <br /> == יחסים בין המחלקה למחלקות אחרות ==<br /> מחלקת ה[[שפה רקורסיבית|שפות הרקורסיביות]] (&#039;&#039;&#039;[[R (מחלקת סיבוכיות)|R]]&#039;&#039;&#039;) היא [[תת-קבוצה]] של &#039;&#039;&#039;RE&#039;&#039;&#039; ו-&#039;&#039;&#039;coRE&#039;&#039;&#039; ולמעשה, R מהווה את החיתוך בין שתי המחלקות, שכן אנו יכולים ל[[כריעות|הכריע]] כל בעיה שקיימת לה מכונת טיורינג המקבלת אותה וקיימת לה מכונת טיורינג הדוחה אותה על ידי הרצה לסירוגין של שתי המכונות עד שאחת מהן עוצרת ופולטת תשובה. לכן:<br /> :&lt;math&gt;\mbox{R} = \mbox{RE}\cap\mbox{coRE}&lt;/math&gt;.<br /> <br /> באופן הפוך, הקבוצה של כלל השפות הפורמליות שאינן ב-RE ואינן ב-coRE נקראת &#039;&#039;&#039;NRNC&#039;&#039;&#039;. זוהי מחלקת כלל השפות הפורמליות שלא קיימת להן מכונת טיורינג היכולה להוכיח או להפריך שייכות אליהן בזמן סופי, כלומר:<br /> :&lt;math&gt;\mbox{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{coRE})&lt;/math&gt;.<br /> <br /> לא רק שבעיות כאלו אינן כריעות, גם הן וגם המשלימות שלהן אינן ניתנות למנייה רקורסיבית.<br /> <br /> == בעיות שלמות ב-RE ==<br /> המחלקה &#039;&#039;&#039;RE-Complete&#039;&#039;&#039; היא תת-קבוצה של המחלקה &#039;&#039;&#039;RE&#039;&#039;&#039; המכילה את כל בעיות ההכרעה שהן שלמות ב-RE. ניתן לומר כי הן הבעיות &quot;הכי&quot; קשות הניתנות למנייה רקורסיבית. באופן כללי, אין הגבלות על ה[[רדוקציה חישובית|רדוקציות]] פרט לכך שהן אמורות להיות פונקציות מלאות המוגדרות לכל קלט ותקפות.<br /> <br /> דוגמאות לבעיות שהן שלמות ב-RE:<br /> # [[בעיית העצירה]]: בהינתן [[תוכנית מחשב]] ו[[קלט]], האם התוכנית תסיים את פעולתה בשלב כלשהו עבור קלט זה.<br /> # [[משפט רייס]] אומר כי הכרעה של שייכות עבור כל תת-קבוצה לא טרוויאלית של קבוצת [[פונקציה בת-חישוב|פונקציות רקורסיביות]] היא RE-קשה. היא תהיה שלמה אם הקבוצה היא ניתנת למנייה רקורסיבית.<br /> # [[ג&#039;ון מייהיל]] {{אנ|John Myhill}} ([[1955]]) הוכיח כי כל ה[[קבוצה יצירתית|קבוצות היצירתיות]] {{אנ|Creative and productive sets}} הן RE-שלמות.<br /> # [[בעיית המילה]] {{אנ|Word problem (mathematics)}} היוניפורמית עבור [[חבורה (מבנה אלגברי)|חבורות]] ו[[חבורה למחצה|חבורות למחצה]].<br /> # קביעת שייכות עבור [[דקדוק בלתי-מוגבל]] {{אנ|Unrestricted grammar}} כללי (טיפוס 0 ב[[היררכיית חומסקי]]).<br /> # בעיית ה[[תקפות (לוגיקה)|תקפות]] עבור [[שפה מסדר ראשון|תחשיב פרדיקטים מסדר ראשון]].<br /> # [[בעיית ההתאמה של פוסט]]<br /> # קביעה אם ל[[משוואה דיופנטית]] יש פתרונות ב[[מספר שלם|שלמים]].<br /> <br /> == בעיות שלמות ב-coRE ==<br /> המחלקה &#039;&#039;&#039;coRE-Complete&#039;&#039;&#039; היא תת-קבוצה של המחלקה &#039;&#039;&#039;coRE&#039;&#039;&#039; המכילה את כל בעיות ההכרעה שהן שלמות ב-coRE.<br /> <br /> דוגמאות לבעיות שהן שלמות ב-coRE:<br /> # [[בעיית הדומינו]] ב[[אריחי ואנג]].<br /> # בעיית ה[[ספיקות]] {{אנ|Satisfiability}} עבור [[שפה מסדר ראשון|תחשיב פרדיקטים מסדר ראשון]].<br /> <br /> == קישורים חיצוניים ==<br /> * {{קישור כללי|כתובת=https://complexityzoo.net/Complexity_Zoo:R#re|הכותב=[[סקוט אהרונסון]]|כותרת=Class RE|אתר=באתר Complexity Zoo|שפה=אנגלית}}<br /> * {{קישור כללי|כתובת=https://complexityzoo.net/Complexity_Zoo:C#core|הכותב=[[סקוט אהרונסון]]|כותרת=Class coRE|אתר=באתר Complexity Zoo|שפה=אנגלית}}<br /> <br /> {{מחלקות סיבוכיות}}<br /> [[קטגוריה:מחלקות סיבוכיות]]</div>

imported>OrF8