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

::הכיוון שהייתי חותר אליו הוא כלהלן:

::*'''מבוא:''' מושג הכריעות (R) הגדרה ומוטיוובציה לשאר החלקים - "מיפוי" עולם השפות לפי כריעות השפה

::*'''אי־כריעות:''' הסבר שיש שפות שאינן כריעות (אינן ב־R) (הוכחה: שיקולי ספירה). דוגמא לשפה לא כריעה: HP בהוכחה ישירה.

::*'''מושג הרדוקציה:''' הסבר שבמקום להוכיח לגבי כל שפה בנפרד, ניתן ליצור יחסים בין שפות. הוכחה של שפת האלכסון ורדוקציה ממנה לשאר השפות (לא הכי קריטי, אפשר לעשות אותו דבר מ־HP. כבר אמרתי שלדעתי ההוכחה של שפת האלכסון "נקייה" הרבה יותר מ־HP. אז אולי כן כדאי להשאיר אותה)

::*'''כריעות למחצה:''' עכשיו נתבונן יותר טוב בעולם שמחוץ ל־R וננסה למפות אותו. כאן ניתן להגדיר את RE ומשלימתה (ראה (*) בהמשך), להרחיב את משפטי הרדוקציה גם לחלקים אלו של העולם, ולהראות קיומן של שפות לא כריעות שכן נמצאות בRE או coRE (או לא בשתיהן, כרגע זה מופיע חבוי בתרגיל).

::*המשך כמו עכשיו - רייס וכו.

::(*) אני לא יודע האם ההגדרה של RE צריכה להיות כל־כך מאוחר, או שעדיף להשאיר אותה, כמו עכשיו, כבר בפסקת המבוא. יש לי דעות לכאן ולכאן.

::שתי נקודות שחשוב לי לציין:

::#אני רוצה להדגיש את חשיבות הרדוקציה – לא מדובר בעוד כלי סתמי, אלא במשהו מהותי ביותר: במקום להוכיח שוב ושוב מחדש לגבי כל שפה, הרדוקציה מאפשרת לנו לבצע את ההוכחה ה"קשה" פעם יחידה, ומשם "לקשור" את השפות אחת לשניה ברדוקציה (אגב, הגרסה הנוכחית חסרה את הרעיון, שהרדוקציה מגדירה יחס של "יותר קשה חישובית"; אח"כ זה מאד הגיוני כשרואים את "מפת העולם" וששפות "קשות" יותר נמצאות יותר גבוה במפה ובצד ה"גדול יותר" של הרדוקציה). העקרון הזה לדעתי מהותי מאד. העקרון הנ״ל חוזר על עצמו גם כשעוסקים בשפות NP שלמות: מוכיחים ששפה אחת היא שלמה (SAT, משפט קוק), ומשם בונים עץ של רדוקציות לשפות אחרות, שכולן NP-שלמות. לכן מבחינתי החלק של הרדוקציה צריך להופיע מוקדם ככל הניתן, ולא בסוף, בתור עוד איזה כלי איזוטרי.

::#המוטיבציה לעיל היא ללכת top-down: קודם כל R מול "לא R", ואח"כ עושים "Zoom-in" לחלק השני ומרחיבים עליו.

::לגבי השיום: לא ראיתי חוסר עקביות. "כריעות" היא תמיד R, ואי־כריעות היא תמיד "לא R". בד״כ בשאר המקומות לא משתמשים במושג "כריעה" אלא רושמים את השייכות במפורש (דהיינו: RE או <math>\Sigma^* \smallsetminus coRE</math>). נושא זה לדעתי פחות חשוב מהשאר ואפשר לתקנו בסוף. {{#תנאי:|&lrm;|&rlm;}}[[משתמש:Gran|gran]]{{#תנאי:|&lrm;|&rlm;}} - [[שיחת משתמש:gran|שיחה]] 06:42, 2 בפברואר 2012 (IST)