שיחה:תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף

::::::'''[[תורת החישוביות/כריעות שפות/ארגז חול|כריעות שפות]]''' - ההגדרה של R צריכה להיות מאוחדת עם הכריעות. ההגדרה עצמה צריכה להיות מפורשת - "R היא כלל השפות להן יש מ״ט ש...". תאר לעצמך קורא שחוזר אל הפרק כדי לוודא שהוא מבין מה זה R, ומגלה ש <math>R= \{ L \;|\; L \text{ recursive} \}</math> - אין בזה שום תועלת. מבחינת העיצוב יש יותר מדי "מסגרות", אישית אני לא אוהב את זה, זה נראה כאילו בפרק אין "תוכן" אלא רק הגדרות ודוגמאות. אני מעדיף להשתמש במסגרות כמה שפחות, ורק על מנת להדגיש חשיבות. כדאי להשלים דוגמא של שפה שנמצאת בcoRE ולהראות את הבנייה של המ״ט המתאימה. את האיור הייתי מוריד לסוף, זו אכן מסקנה מהתכונות שראינו. שים לב ש<math>\Sigma^*</math> היא שפה ולא קבוצת שפות - צריך לתקן את האיור.

::::::'''[[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות/ארגז חול|קיום שפות לא כריעות]]''' - בפסקת המבוא: יש "מחלקה" נוספת שהיא "מחוץ" ל־RE ול־coRE, ואנחנו מראים שגם בה יש שפות. ההוכחה של <math>\Sigma^*\setminus RE</math> צריכה להיות מוחלפת ב<math>\Sigma^*\setminus (RE \cup coRE)</math> (גם כאן <math>\Sigma^*</math> זה לא המינוח הנכון). אחרי ההוכחה של HP צריך לסכם שראינו שהיא כן בRE וההוכחה אומרת שהיא לא בR, מכך נובע שהיא ב<math>RE\smallsetminus R</math>. עכשיו אפשר לעשות אותו דבר עם (משלימת) שפת האלכסון וזה מוכיח שיש שפה ב<math>coRE \smallsetminus R</math>. מעולה!. לגבי ההוכחה של שיקולי ספירה - העיצוב בעייתי והסדר הפוך. תשאיר לי לשנות את זה, אם אתה רוצה.

 

::::::אני מסכים עם שאר הדברים שכתבת, ואתה מוזמן לעשות את השינוי המבני לפי מה שהצעת. {{#תנאי:|&lrm;|&rlm;}}[[משתמש:Gran|gran]]{{#תנאי:|&lrm;|&rlm;}} - [[שיחת משתמש:gran|שיחה]] 06:23, 4 בפברואר 2012 (IST)