שיחה:תורת החישוביות/כריעות שפות

בעיית העצירה

יש קצת חוסר אחידות, לדעתי, בזה שמגדירים את משפחת הקלטים העוצרים בתור "בעיית העצירה". "בעיית העצירה" היא הבעיה (הבלתי נתנת לפתרון) של מציאת משפחה זו, לא המשפחה עצמה. Atavory - שיחה 23:36, 22 בינואר 2012 (IST)

כמו שראית ב"שקילות מודל הכרעה", שני הנ״ל שקולים – HP היא השפה (במודל ה"הכרעה") שמתארת את (מה שאתה קורא) "בעיית העצירה". ‏gran‏ - שיחה 23:43, 22 בינואר 2012 (IST)

אנא, אל תעשה שינויים כגון אלה לפני דיון בדף השיחה. השם HP הוא מינוח מאד נפוץ בספרות לבעיית העצירה, ושאר הספר משתמש בו הרבה. עדיף שלא לפגוע בעקביות של הספר. ‏gran‏ - שיחה 23:52, 22 בינואר 2012 (IST)

אהלן, לגבי ההבדל בין H לHP, ניסיתי ללכת לפי פפדימיטריו (שגם עושה זאת), ולדעתי ההבחנה מקלה על הדיון: קצת מוזר לדבר על הבעיה האם משהו שייך לHP, כשHP כבר מוגדרת בתור בעיה (ולא כקבוצה). לגבי העקביות, זו הסיבה שסימנתי את הדפים האחרים כנמצאים בעבודה, כדי שאוכל לשנות גם שם לעקביות. בינתיים השארתי את הדברים כHP, לבקשתך. אשמח לדון על שינויי בדף ששחזרת: לדעתי יש בהם הגיון דוקא. תודה, Atavory - שיחה 11:31, 23 בינואר 2012 (IST)

אני לא רואה בעיה לעשות overloading בין השפה ל"בעיה", שהרי שניהם אותו הדבר. אני לא זוכר מה סיפסר עושה (אני יכול לבדוק מחר); אולי אפשר לקרוא לשפה $L_{HP}$. מיותר, לדעתי, אבל אין לי בעיה אם אתה מעדיף. H נראה ממש חסר הגיון.

H מופיע בעוד ספרים, לדוגמה של הארי לואיס, בנוסף לזה של פפדימיטריו. HP כסימון לקבוצה, לא לבעיה, לא ראיתי באף ספר מודפס, וגם לא Overloading אחר בין הקבוצה לבין הבעיה. אני מציע שנתפשר על $L_{HP}<m$, אם כך. מה דעתך? Atavory - שיחה 23:42, 25 בינואר 2012 (IST)

לא מתנגד ל־$L_{HP}$. ‏gran‏ - שיחה 09:05, 26 בינואר 2012 (IST)

שמת "בעבודה" על כמה דפים. לא עדיף לעבוד פרק פרק, פרה פרה? שום דבר לא בוער, וחוץ ממני (וממך) אף אחד לא ישנה דבר. ‏gran‏ - שיחה 09:28, 24 בינואר 2012 (IST)

עברתי על השינויים שוב, בהחלט הייתי פזיז מדי בשחזור. צריך להחזיר את ההגדרות. מצטער. ‏gran‏ - שיחה 09:39, 24 בינואר 2012 (IST)

אהלן, זה היה רק ליום אחד, כמדומני, ועל שינויים רוחביים (לדעתי) בבערך 3-4 דפים. השארתי עכשיו שניים על דפים חדשים שאין לי זמן לעבוד עליהם. אם היתה תבנית "בבניה" - דהיינו משהו שאומר שאין תוכן שלם בדף אבל אין בלעדיות, הייתי מוסיף זאת שם. יש כזאת? תודה, Atavory - שיחה 10:05, 24 בינואר 2012 (IST)

רשימת השפות בראש העמוד

אפילו לא הייתי מעלה את זה, מפני שזה טריוויאלי, אבל השינוי הקודם שלי בעניין כבר שוחזר. מדוע השפות הרגולריות מופיעות בסוגריים? אם זה מחמת חוסר חשיבות העניין, אז הדוגמה שלאחריהן חשובה אפילו פחות. Atavory - שיחה 00:29, 27 בינואר 2012 (IST)

לא, לא בגלל שזה לא חשוב :) הסיבה היא אחרת – לא הגדרנו מהם שפות רגולריות, ואולי הקורא לא מכיר את אוטומטים ושפות פורמליות. לכן זה מאמר מוסגר: הקורא מבין – יופי. הקורא לא מבין – לא קרה שום דבר... ‏gran‏ - שיחה 06:44, 2 בפברואר 2012 (IST)

אוקיי, אבל אז נראה לי שכדאי לציין את זה בסוגריים, נניח "(למי שמכיר אוטומטים ושפות פורמאליות, שפות רגולריות, וכו' וכו')". אני עובד על דף בארגז חול בינתיים, ואוסיף את זה שם. Atavory - שיחה 10:27, 3 בפברואר 2012 (IST)

ארגון מחודש של החלק

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

1. לחלק את החלק כך:
   1. הדף הראשון (זה) ישונה לדף הסברים והגדרות על מחלקות הכריעות השונות (R, RE, coRE) + יכיל מבט-על על החלק.
   2. הדף השני (זה שנקרא כעת "שפות שאינן כריעות") ישונה לשם "ייחסים בין מחלקות השפות", וחלק מהחומר בדף זה יעבור אליו.
   3. דף הרדוקציה יעבור בסדרו אחריו, וחלק מהחומר בדף "שפות שאינן כריעות" יעבור אליו.
   4. שני הדפים האחרונים (רייס + אי-הפרדתיות) יישארו כפי שהם.
2. להחליט על אחידות גבוהה יותר בעניין ה"כריעות".

לדעתי יש לכך מספר יתרונות:

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

Atavory - שיחה 14:40, 1 בפברואר 2012 (IST)

טוב, הצעתי לדף זה נמצאת בתורת החישוביות/כריעות שפות/ארגז חול. Atavory - שיחה 00:26, 2 בפברואר 2012 (IST)

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

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

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

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

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

לגבי השיום: לא ראיתי חוסר עקביות. "כריעות" היא תמיד R, ואי־כריעות היא תמיד "לא R". בד״כ בשאר המקומות לא משתמשים במושג "כריעה" אלא רושמים את השייכות במפורש (דהיינו: RE או $\Sigma ^{*}\smallsetminus coRE$). נושא זה לדעתי פחות חשוב מהשאר ואפשר לתקנו בסוף. ‏gran‏ - שיחה 06:42, 2 בפברואר 2012 (IST)

אוקיי, נראה לי שאפשר להגיע לעמק השווה, ודווקא בלי שינויים ענקיים. לפני זה, אבל, מה בעצם רוצים שייצא מחלק זה? נראה לי כך:

1. הכרה שיש בעיות לא כריעות ולא כריעות למחצה (והרבה מהן)
2. יכולת שימוש במשפטים, בפרט משפט הרדוקציה
3. הבנה של מבנה העולם של מחלקות הכריעות.

כעת פשוט צריך לארגן את החומר לפרקים קוהרנטיים עם תלויות מתקבלות על הדעת, ומינימום דילוגים וחזרות. ישנם האילוצים הבאים:

1. לרדוקציה צריך להכיר את מחלקות הכריעות, גם אם לא את היחסים ביניהם.
2. כדי להוכיח שיש (או אפילו רוב) השפות אינן בRE, יש צורך בעוצמות.
3. כדי לטעון שמהעובדה שיש שפות שאינן בRE, גם יש שפות שאינן בR, יש צורך לדעת שR חלק מRE. אפשר אמנם להשתמש באותה הוכחה ישירות על R, בלי להזכיר כלל את RE בשלב זה, אלא שאני חושב שמיותר להשתמש במניה כדי להוכיח שיש שפות שאינן בR, ופתאום לקראת סוף הפרק להגיד "בעצם רעיון די דומה מוכיח שיש שפות שאינן בRE".

הייתי מציע לכן את המבנה הבא, שדי דומה למבנה הנוכחי:

1. מבוא (די דומה לפרק בארגז החול)
2. אי כריעות (מלאה ולמחצה) - די דומה לפרק הנוכחי שפות בלתי כריעות. הבנתי שיש לך ביקורת על מבנה הפרק הנוכחי, לא הבנתי כלל מהי. אני לא רואה מה יש לשנות בו כ"כ (בודאי שאינני רואה סיבה לחזור).
3. רדוקציה (די דומה לפרק הנוכחי)
4. מבנה מחלקות השפות (מקבל חלקים מפרק המבוא הנוכחי)
5. משפט רייס (די דומה לפרק הנוכחי)
6. אי-הפרדתיות - (די דומה לפרק הנוכחי)

לדעתי די מתאים למה שאמרת, אם שינויים קלים. מה דעתך?Atavory - שיחה 14:19, 2 בפברואר 2012 (IST)

אני חושב שצריך להחליף בין "2" ל"3", מהסיבות שרשמתי לעיל, אם ב"2" יש יותר מאשר הגדרות ותכונות בסיסיות (סגירות וכו). לגבי הפרק של אי כריעות, אני ארשום שם מה מפריע לי בו. ‏gran‏ - שיחה 06:33, 3 בפברואר 2012 (IST)

איך שאני רואה את זה, סגירות וכו' זה ב4. לגבי שפות לא כריעות, ארשום שם גם. כל טוב,Atavory - שיחה 10:29, 3 בפברואר 2012 (IST)

אהלן, חשבתי ועבדתי די הרבה על הדברים, ואני מקווה שהתוצאה משלבת בין הנקודות שהעלינו. היא נראית כך (בסדר זה):

• כריעות שפות
  • קיום שפות לא כריעות
  • רדוקציה
  • משפט רייס
  • אי-הפרדתיות רקורסיבית

אני מסכים אתך לגבי הדברים הבאים:

1. ישנו בלגאן כלשהו בקיום שפות שאינן כריעות/ארגז חול (לא שמתי לב אליו לפני כן, אשמח מאד אם תתקן)
2. שפות לא כריעות אולי מסודר, אבל הפך קצת לרשימת מכולת (אני מסייג שזה היה תוך כדי עבודה על כל החלק)

מצד שני, נראה לי שהנקודות הבאות הן מאד לטובת ההצעה החדשה:

1. אינני חושב שטוב שחלק הרדוקציה יגיע לפני החלק המראה כלל שיש שפות לא כריעות. המשפט הפותח מדגים את הבעייתיות "כצעד ראשון לקראת ההוכחה ששפות מסוימות אינן כריעות" - הרדוקציה, לטעמי, איננה כלל הצעד הראשון לקראת ההוכחה שיש שפות כאלו. לאחר שהוכח שיש שפות כאלה, הרדוקציה היא כלי טרנזיטיבי לתכונה זו. אני חושב שהסדר החדש משקף זאת טוב יותר, במקום forward-referencing שיש עכשיו בחלק על רדוקציה.
2. תמונת העולם של מחלקות הכריעות, שהוא לטעמי חלק די מרכזי בחלק זה, איננו תוצר לוואי של קיום שפות לא כריעות.

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

כל טוב, Atavory - שיחה 15:47, 3 בפברואר 2012 (IST)

היי, זה בהחלט בכיוון. נעלמה לי ההוכחה ש(המשלים של) שפת האלכסון אינה כריעה. כנראה נשמטה.. (בלעדיה, כל שרשרת הרדוקציות חסרות משמעות). אני אסתכל על זה קצת יותר לעומק בזמן הקרוב. ‏gran‏ - שיחה 03:36, 4 בפברואר 2012 (IST)

כמה הערות שיש לי:

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

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

רדוקציה - אולי להחליף את השם? מה דעתך על "רדוקציה חישובית, ושפות לא כריעות" (טוב, זה מוגזם. אולי רק "רדוקציה חישובית"). את הדוגמאות שבסוף הפרק צריך לשים תחת כותרת מתאימה כגון "שימושים ברדוקציה" או משהו כזה. שוב ההערה על ריבוי־יתר של המסגרות. לבסוף הייתי חוזר על איור "תמונת העולם" כשעליו מופיעות השפות השונות במיקום המתאים. להוסיף דוגמא/תרגיל: שפות שאינן ב־$RE\cup coRE$ כגון $L_{\Sigma ^{*}}$.

אני מסכים עם שאר הדברים שכתבת, ואתה מוזמן לעשות את השינוי המבני לפי מה שהצעת. ‏gran‏ - שיחה 06:23, 4 בפברואר 2012 (IST)

שלום, עם רובן המכריע של הערותיך אני מסכים. יש דברים שהם בברור שגויים כעת (כמו סיגמה כוכבית כקבוצת שפות, לדוגמה). ישנם עניינים של טעם, כמו האם השימוש במסגרות הוא חיובי ובאיזה מידה (נראה שדעתי שונה משלך), אבל נלך לכוונך. אם לא אכפת לך, רק הייתי רוצה להתעקש על התרשים של תמונת העולם של המחלקות בראש התכונות, לא בסוף (למרות שגם זה עניין של טעם). אני ניגש לכן לשינוי המבני. לגבי הערותיך כאן: את חלקן הכנסתי כבר, ואת חלקן אעשה בימים הקרובים. כל טוב, Atavory - שיחה 22:56, 4 בפברואר 2012 (IST)

טוב, ערכתי את השינוי המבני בגדול. ישנן ההערות שציינת, ונראה לי שלמרות מאמצי יש גם קישורים שבורים פה ושם. נראה לי שאטפטף את השינויים בימים הקרובים. שבוע טוב, Atavory - שיחה 23:06, 4 בפברואר 2012 (IST)

בסדר, תגיד לי כשתסיים עם ההעברות וההעתקות, ואני אעבור על זה שוב ואשלים תיקונים. לגבי המסגרות, כפי שאמרתי זו דעתי האישית ובהחלט זה עניין של טעם. הייתי מבקש שהעיצוב יהיה תואם לשאר הפרקים של הספר. לגבי האיור - לא אכפת לי. לגבי קבוצת כל השפות, צריך להגדיר אותה איפשהו ולכנות אותה בשם. הייתי מעדיף שם פשוט ולא 2-בחזקת-סיגמא. למשל universe או $ALL_{\Sigma }=\{L\mid L\subseteq \Sigma ^{*}\}$. שבוע טוב, ‏gran‏ - שיחה 03:33, 5 בפברואר 2012 (IST)

העתקה ולא העברה

כדי לא למחוק את היסטוריית הגרסאות (ובשביל לשמור את דפי השיחה), העברתי את הדפים הישנים למקומם החדש לפי רה-ארגון לעיל, ואת טיוטת ההצעה שלך לארגז חול. על-מנת להשלים את הרה-ארגון אנא העתק את השינויים לדפים המתאימים, ומחק את ארגזי החול (אני יכול להעתיק בעצמי, אבל אני מעדיף שהקרדיט לסידור מחדש יהיה שלך). ‏gran‏ - שיחה 03:59, 8 בפברואר 2012 (IST)

אהלן, העברתי. לגבי קרדיט: אני מקווה שברור מי בעצם כתב את הדפים (רמז: אתה). בהצלחה עם ההמשך. כל טוב, Atavory - שיחה 13:01, 8 בפברואר 2012 (IST)