שיחה:תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 47:
::#המוטיבציה לעיל היא ללכת top-down: קודם כל R מול "לא R", ואח"כ עושים "Zoom-in" לחלק השני ומרחיבים עליו.
::לגבי השיום: לא ראיתי חוסר עקביות. "כריעות" היא תמיד R, ואי־כריעות היא תמיד "לא R". בד״כ בשאר המקומות לא משתמשים במושג "כריעה" אלא רושמים את השייכות במפורש (דהיינו: RE או <math>\Sigma^* \smallsetminus coRE</math>). נושא זה לדעתי פחות חשוב מהשאר ואפשר לתקנו בסוף. {{#תנאי:|‎|‏}}[[משתמש:Gran|gran]]{{#תנאי:|‎|‏}} - [[שיחת משתמש:gran|שיחה]] 06:42, 2 בפברואר 2012 (IST)
::: אוקיי, נראה לי שאפשר להגיע לעמק השווה, ודווקא בלי שינויים ענקיים. לפני זה, אבל, מה בעצם רוצים שייצא מחלק זה? נראה לי כך:
:::#הכרה שיש בעיות לא כריעות ולא כריעות למחצה (והרבה מהן)
:::#יכולת שימוש במשפטים, בפרט משפט הרדוקציה
:::#הבנה של מבנה העולם של מחלקות השקילות.
:::כעת פשוט צריך לארגן את החומר לפרקים קוהרנטיים עם תלויות מתקבלות על הדעת, ומינימום דילוגים וחזרות. ישנם האילוצים הבאים:
:::#לרדוקציה צריך להכיר את מחלקות השקילות, גם אם לא את היחסים ביניהם.
:::#כדי להוכיח שיש (או אפילו רוב) השפות אינן בRE, יש צורך בעוצמות.
:::#כדי לטעון שמהעובדה שיש שפות שאינן בRE, גם יש שפות שאינן בR, יש צורך לדעת שR חלק מRE.
:::הייתי מציע לכן את המבנה הבא, שדי דומה למבנה הנוכחי:
:::#'''מבוא''' (די דומה לפרק בארגז החול)
:::#'''אי כריעות (מלאה ולמחצה)''' - די דומה לפרק הנוכחי שפות בלתי כריעות. אני חושב שמיותר להשתמש במניה כדי להוכיח שיש שפות שאינן בR, ופתאום לקראת סוף הפרק להגיד "בעצם רעיון די דומה מוכיח שיש שפות שאינן בRE". הבנתי שיש לך ביקורת על מבנה הפרק הנוכחי, לא הבנתי כלל מהי. אני לא רואה מה יש לשנות בו כ"כ (בודאי שאינני רואה סיבה לחזור).
:::#'''רדוקציה''' (די דומה לפרק הנוכחי)
:::#'''מבנה מחלקות השפות''' (מקבל חלקים מפרק המבוא הנוכחי)
:::#'''משפט רייס''' (די דומה לפרק הנוכחי)
:::#'''אי-הפרדתיות''' - (די דומה לפרק הנוכחי)
:::לדעתי די מתאים למה שאמרת, אם שינויים קלים. מה דעתך?[[משתמש:Atavory|Atavory]] - [[שיחת משתמש:Atavory|שיחה]] 14:19, 2 בפברואר 2012 (IST)
| |||