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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 66:
::::אני חושב שצריך להחליף בין "2" ל"3", מהסיבות שרשמתי לעיל, אם ב"2" יש יותר מאשר הגדרות ותכונות בסיסיות (סגירות וכו). לגבי הפרק של אי כריעות, אני ארשום שם מה מפריע לי בו. {{#תנאי:|‎|‏}}[[משתמש:Gran|gran]]{{#תנאי:|‎|‏}} - [[שיחת משתמש:gran|שיחה]] 06:33, 3 בפברואר 2012 (IST)
:::::איך שאני רואה את זה, סגירות וכו' זה ב4. לגבי שפות לא כריעות, ארשום שם גם. כל טוב,[[משתמש:Atavory|Atavory]] - [[שיחת משתמש:Atavory|שיחה]] 10:29, 3 בפברואר 2012 (IST)
:::::אהלן, חשבתי ועבדתי די הרבה על הדברים, ואני מקווה שהתוצאה משלבת בין הנקודות שהעלינו. היא נראית כך (בסדר זה):
:::::*[[תורת החישוביות/כריעות שפות/ארגז חול|כריעות שפות]]
:::::**[[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות/ארגז חול|קיום שפות לא כריעות]]
:::::**[[תורת החישוביות/כריעות שפות/רדוקציה/ארגז חול|רדוקציה]]
:::::**[[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]]
:::::**[[תורת החישוביות/כריעות שפות/אי-הפרדתיות רקורסיבית|אי-הפרדתיות רקורסיבית]]
:::::אני מסכים אתך לגבי הדברים הבאים:
:::::#ישנו בלגאן כלשהו ב[[תורת החישוביות|קיום שפות שאינן כריעות/ארגז חול]] (לא שמתי לב אליו לפני כן, אשמח מאד אם תתקן)
:::::#[[תורת החישוביות|שפות לא כריעות]] אולי מסודר, אבל הפך קצת לרשימת מכולת (אני מסייג שזה היה תוך כדי עבודה על כל החלק)
:::::מצד שני, נראה לי שהנקודות הבאות הן מאד לטובת ההצעה החדשה:
:::::#אינני חושב שטוב שחלק הרדוקציה יגיע לפני החלק המראה כלל שיש שפות לא כריעות. המשפט הפותח מדגים את הבעייתיות "כצעד ראשון לקראת ההוכחה ששפות מסוימות אינן כריעות" - הרדוקציה, לטעמי, איננה כלל הצעד הראשון לקראת ההוכחה שיש שפות כאלו. לאחר שהוכח שיש שפות כאלה, הרדוקציה היא כלי טרנזיטיבי לתכונה זו. אני חושב שהסדר החדש משקף זאת טוב יותר, במקום forward-referencing שיש עכשיו בחלק על רדוקציה.
:::::#תמונת העולם של מחלקות הכריעות, שהוא לטעמי חלק די מרכזי בחלק זה, איננו תוצר לוואי של קיום שפות לא כריעות.
:::::אני די מקווה שהשילוב, שבהחלט לקח בחשבון את הערותיך, בסדר מבחינתך. ישנה נקודה בה ניסיתי לללכת בכוון אותו הצעת, אבל לא היה אפשר לללכת אתו עד הסוף: אם תבדוק את התלויות בנושאים, תראה שאין ממש אפשרות להציג את RE לאחר הנושאים האחרים: זה היה יוצר כפילויות ודילוגים אדירים.
:::::כל טוב, [[משתמש:Atavory|Atavory]] - [[שיחת משתמש:Atavory|שיחה]] 15:47, 3 בפברואר 2012 (IST)
חזרה לדף "תורת החישוביות/כריעות שפות".