שיחה:קבוצה ניתנת למנייה רקורסיבית

אני חושבת שהמושג כריעה למחצה הרבה יותר נפוץ מכריעה חיובית. נא לשקול להחליף את "כריעה חיובית" ב"כריעה למחצה". ג'ודי אבוט - שיחה 01:59, 16 במאי 2008 (IDT)

טיוטה - הרחבת ההקדמה

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

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

שפה $L\in RE$ אם ורק אם היא כריעה חיובית. RE היא קבוצת כל השפות הכריעות חיובית.

שפה $L\in co-RE$ אם ורק אם היא כריעה שלילית. co-RE היא קבוצת כל השפות הכריעות שלילית.

שפה $L\in R$ אם ורק אם היא כריעה חיובית וגם כריעה שלילית, כלומר קיים אלגוריתם עבורו המכונה תעצור בהכרח עבור כל מילת קלט. במילים אחרות, $RE\cap co-RE=R$. R היא קבוצת כל השפות הרקורסיביות.

שפה $L\in RE\setminus R$ אם ורק אם היא כריעה חיובית אך לא כריעה שלילית, כלומר לא ניתן להכריע במופע שלילי. באופן דומה, גם לכריעה שלילית.

כשקראתי קצת פה, הבנתי שלא למדתי על הנושא לעומק. הכרתי את ההגדרה של שפות רקורסיביות וניתנות למנייה רקורסיבית, אך לא הגדרה שכזאת על קבוצה. האם מדובר בסה"כ בתת קבוצה של RE, או הכללה של המושג לכל קבוצה של איברים פשוטים, במקום על מילים? ההגדרות פה עוסקות בקבוצות ולא בשפות, אך לא קיים הבדל מהותי ביניהם, כי האיברים המדוברים הם לא שפות או קידודי מכונות. (¯`gal´¯) - שיחה 20:11, 18 בנובמבר 2019 (IST)

הערה: נראה לי שהסימון „שפה $L\in RE$״ רק מבלבל. אפשר במקום זה לכתוב „שפה שייכת ל־RE״ וזה ברור יותר לא רק למי שבמקרה לא מכיר את הסימון. Tzafrir - שיחה 14:13, 20 בנובמבר 2019 (IST)

ממה שהבנתי ההגדרה הזאת היא על קבוצות ולא על שפות, למרות שלא הכרתי את זה. כנראה שהניסוח צריך להיות מתאים לקבוצות. השוני בין שפות לקבוצות הוא די מינורי, ומתבטא בעיקר בהגדרה ובסימון של דברים, כך שלא ברור לי מה הנחיצות בשתי הגדרות. ראיתי שההגדרה של שפה רקורסיבית בנויה על ההגדרה של קבוצה רקורסיבית, כך שכנראה היה פה עניין ליצור הגדרה יותר כללית, אך מאפייניה, וכל המשפטים הנובעים ממנה די זהים. כמו כן, ראיתי שבגרסה האנגלית גם כן יש שוני בפונקציה שהגדירו, כך שתתאים גם לרעיון שהמכונה יכולה לעצור. אגב, גם בהגדרה הפורמלית הזאת של הפונקציה לא נתקלתי. לא רואה למה ההגדרה המילולית לא מספקת. עוד דבר, בפונקציה מקבלים מצב שהמכונה לא עוצרת, דבר שמוסבר במילים, אך היא מוגדרת כניתנת לחישוב. דברים דומים לזה ראיתי רק ברדוקציות. (¯`gal´¯) - שיחה 16:45, 21 בנובמבר 2019 (IST)

שפה היא קבוצת מילים. כלומר שפה היא אוסף של רצפי אותיות מאלף־בית נתון. Tzafrir - שיחה 18:48, 21 בנובמבר 2019 (IST)