שיחה:תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות

רציונאל לשינויים המבניים בחומר המשובח שכבר הופיע כאן

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

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

Atavory - שיחה 17:06, 24 בינואר 2012 (IST)

בהתאם למספור שלך,

1. מסכים. גישת top-down עדיפה. לרוב מה שחסר הוא פסקת "מוטיבציה". דווקא כאן הייתה בהתחלה שורה של "מוטיבציה" (האם קיימות שפות לא כריעות). לדעתי, תמונת העולם היא המסקנה של הפרק, ולא המוטיבציה אליו, ועל־כן אמורה להופיע בסוף, ולא בראש. מה שחסר בראש הוא פסקה כתובה שמציעה את הרעיון (שאינו "הגיוני" כלל וכלל!), שהמחשב הוא מוגבל, ויש דברים שהמחשב אינו יכול לעשות. (למעשה – זו הפעם הראשונה שמישהו אמר לי שיש דברים שמחשבים לא יכולים לעשות. עד אז חשבתי לתומי שעם קצת מאמץ, קצת טכנולוגיה וקצת זמן – הכל אפשרי). לאחר מכן צריכות לבוא ההוכחות. לבסוף, מסכמים עם "תמונת העולם" כפי שאנחנו מבינים לאחר ההוכחות שראינו..
2. זה עניין של טעם. בבסיס, שתי ההוכחות זהות: יצירת סתירה ע״י הפניה עצמית. הגישה של שפת האלכסון יותר ברורה מכיוון שהיא מקבילה באופן כמעט מושלם לשיטת הלכסון של קנטור. גם בHP מתבצעת אותה פעולה, אבל זה "מוחבא" מתחת לפני השטח (וההוכחה יותר מורכבת: דורשת עוד רמה של מ״ט, לעומת מ״ט יחידה בשפת האלכסון). מצד שני, ההוכחה הישירה של HP מוכרת מאד ונפוצה מאד, ואין מניעה להביא אותה גם כאן. (אנקדוטה: כשלמדתי את הקורס, הדוגמא של HP הובאה בשיעור הראשון (כרעיון כללי, ללא ניסוח ע״י מ״ט), ובגלל שהייתה כ״כ מדהימה, גרמה לי להנות משאר הקורס הרבה יותר. אולי אפשר להזיז אותה גם כאן לדף המבוא, כדי לתת מוטיבציה למה הקורס עוסק ואח״כ להפנות חזרה אליה בפרק הזה). אני לא חושב שיש טעם בשתי ההוכחות זו לצד זו – אחת מהן יכולה להפוך לתרגיל או לאתגר.
3. לא בדיוק הבנתי אותך. לא צריך לדעת מה השם של כל עוצמה, אבל צריך להבין שיש "רמות שונות של אינסוף" ואין כל מניעה לתת לזה את השם הנכון.
4. מסכים, לא קל להוסיף איורים. אבל אפשרי, ואם משתמשים בפורמט נוח, אז גם אחרים יכולים לערוך (ע״י תוכנה גרפיקה מתאימה). היה יכול להיות יותר נחמד, עם היה אפשר לקודד ישירות בלאטך (PGF/Tikz) והאיור היה מתרנדר בעת הצפיה.

עוד הערות לפרק הנ״ל:

• עדיף שאיורי הקבוצות יהיו צבעוניים. לא יודע למה החלפת את האיור שהיה במשהו שלאו דווקא יותר ברור..
• הנושא של "יותר שפות ממחרוזות" הוא נושא צדדי. בגלל זה הוא היה בתיבה צדדית. לדעתי חשוב להבהיר זאת. היופי בו שהוא נותן את העקרון של הלכסון שאח״כ משתמשים בו להוכחת אי־כריעות. אולי כדאי להפוך אותו לתיבה מוסתרת?
• תודה ששינית לסימולים בהם השתמשתי עד כה. אני רואה שעדיין לא שינית את נושא המקפים והגרשיים – אולי מכיוון שאינך מכיר את פריסת המקלדת החדשה שהופכת את כתיבתם לתהליך קל ונוח (ראה: [1])?

עד כאן, ‏gran‏ - שיחה 04:18, 25 בינואר 2012 (IST)

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

Atavory - שיחה 11:13, 25 בינואר 2012 (IST)

אני לא מצליח להבין את הדף הנוכחי. הוא מבולגן, וחלקי. המצב הקודם היה יותר מובן (לדעתי) אבל גם חלקי משהו, כי חסר בו הבחנה יותר עדינה של מה נמצא מחוץ ל־R. אני לא מצליח להבין את הכיוון הדידקטי אליו אתה מכוון כרגע. אתה רוצה לנסות לשנות, או שאני אבנה מחדש (כנראה על־בסיס הגרסא הקודמת, מפני שאני מתחבר לרציונל שלה הרבה יותר)? ‏gran‏ - שיחה 06:32, 28 בינואר 2012 (IST)

לא הצלחתי להבין מה לא הצלחת להבין + מה גורם לך לחשוב שהוא מבולגן וחלקי (בודאי שלא הצלחתי להבין מדוע זה נאמר כך יחסית לגרסה הקודמת). הדף מסביר בפסקה הראשונה שנושאו הוא תמונת העולם של המחלקות: מטרת הדף ברורה לדעתי, ואף אפשר למצוא בו בקלות את נקודות המשנה, לדוגמה היכן רואים שיש שפות מחוץ לR. לדעתי כל מבנה החלק "כריעות" עדיין מבולגן (ראה שיחה:תורת_החישוביות/כריעות_שפות), וחלק מזה עדיין נותר בדף כאן (אם כי בצורה פחותה מאשר מקודם): היחס בין coRE, RE, וR, לדוגמה, יושב בכלל בדף אחר. לטעמי, זה עדיין עדיף על מה שהיה מקודם, בו גם זה היה, וגם העובדה שיש שפות מחוץ לR בכלל היתה מוטמעת פנימה, משום מה. לגבי החלקיות: א. לא ציינת מה חסר. ב. אם חסר - אפשר להוסיף. Atavory - שיחה 11:07, 1 בפברואר 2012 (IST)

לדעתי הדף כרגע לא טוב. אני אנסה לשנות בימים הקרובים. ‏gran‏ - שיחה 05:14, 1 בפברואר 2012 (IST)

לדעתי הוא משמעותית יותר מסודר ומובן ממה שהיה מקודם, למעט מה שכתבתי מקודם וטרם התייחסת. את הערותי העברתי בינתיים לשיחה:תורת_החישוביות/כריעות_שפות. אינני חושב שהנימוק "לדעתי לא טוב" מסביר את המוטיווציה לשנות. את הבעיות בגרסה הקודמת הסברתי בהרחבה, ואתה מוזמן לעשות זאת גם כן. Atavory - שיחה 09:11, 1 בפברואר 2012 (IST)

הלהלן הבעיות:

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

תמונת העולם הצבעונית

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

נראה לי שיש שלוש קטגוריות בנקודות שלך:

1. נקודות שנוגעות למבנה הפרק
2. נקודות שנוגעות לתוכן תתי-הפרקים
3. האיורים

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

לגבי תוכן תתי-הפרקים, לא בדיוק מסכים, אבל בא נעשה את זה כדעתך.

לגבי האיורים, יש מספר נקודות: א. לי מאד חשוב להדגיש בחלק זה את תמונת העולם של המחלקות, בפרט מה תת-קבוצה של מה, ובפרט מה תת-קבוצה של הקבוצה האוניברסאלית, ב. אין לי קוד המקור של האיורים (בשמחה אשלח את קבצי הoo-draw של המקורות שלי), ואפטיווית, אינני רואה איך אפשר לערוך איורים בלי לדרוס - זה מאד מצער ג. נראה לי שיש טעם שתהיה אחידות באיורים בספר (שוב, חוזר לסעיף ב' + ציירתי עוד + יש עוד מתוכננים)

Atavory - שיחה 10:41, 3 בפברואר 2012 (IST)

אוקיי. הצעתי נמצאת בתורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות/ארגז חול. הדף, לדעתי, מתייחס לנקודות שהעלית. עם זאת, נראה לי עדיף שנמשיך את העניין בשיחה:תורת החישוביות/כריעות שפות#ארגון מחודש של החלק, מפני שקשה לנתק בין הדברים. Atavory - שיחה 15:26, 3 בפברואר 2012 (IST)

דף תרגילים

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

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

בקיצור, לתבנית יש הצדקה בתרגילי הבהרה מוטמעים בטקסט, אך פחות בתרגילי סיכום. Atavory - שיחה 11:42, 26 בינואר 2012 (IST)

שמתי אחד לדוגמה בתורת_החישוביות/כריעות_שפות/שפות_שאינן_כריעות/תרגילים/ארגז_חול. Atavory - שיחה 12:07, 26 בינואר 2012 (IST)

בהחלט! ‏gran‏ - שיחה 18:47, 26 בינואר 2012 (IST)

אהלן, תוכל להזכיר לי בבקשה איך מעבירים דפים? עברו כמה שנים, ושכחתי... תודה, Atavory - שיחה 20:34, 26 בינואר 2012 (IST)

טוב, לא משנה. מצאתי כבר. Atavory - שיחה 20:21, 27 בינואר 2012 (IST)

הוכחה לאי כריעות בעיית העצירה, בקשת עזרה

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

בכריעות למחצה חיובית, ראינו את שפת בעיית העצירה, $L_{\text{HP}}$. נראה ששפה זו איננה כריעה (זו למעשה פורמליזציה של מה שראינו בחלק המוטיווציה במבוא לספר).

טענה:           השפה $L_{\text{HP}}$ אינה כריעה,     $L_{\text{HP}}\notin R$

הוכחה: נניח, על דרך השלילה, שקיימת מ"ט המכריעה את $L_{\text{HP}}$, כלומר, לכל קלט $(\langle M\rangle ,x)$ המכונה עוצרת ומקבלת/דוחה בהתאם לשאלה 'האם המכונה $M$ עוצרת על קלט $x$'. נקרא למכונה זו $H$. כעת נבנה את המכונה $H'$ באופן הבא:

1. בהנתן הקלט קידוד מ"ט $M$, המכונה קודם תריץ את $H(\langle M\rangle ,\langle M\rangle )$, (נזכור שתמיד חלק זה עוצר, שכן הנחתנו בשלילה היא שהבעיה כריעה, ו־$H$ מימוש שלה).
2. אם התשובה חיובית, אז $H'$ תכנס ללולאה אינסופית. אחרת, היא תעצור.

כעת נקבל מצב אבסורד לגבי הריצה של $H'$ על הקלט $x=\langle H'\rangle$, כלומר עבור ההרצה $H'(\langle H'\rangle )$:

1. אם המכונה עוצרת בהרצה זו, אז בהכרח $H(\langle H'\rangle ,\langle H'\rangle )$ החזירה תשובה שלילת (מפני שהיא השלב הראשון בריצת $H'$ שכתוצאתו הוחלט לעצור). אבל לפי ההגדרה, משמעות תשובה שלילית זו היא ש־$H'(\langle H'\rangle )$ איננה עוצרת, ולכן יש סתירה.
2. לעומת זאת, אם המכונה איננה עוצרת בהרצה זו, אז בהכרח $H(\langle H'\rangle ,\langle H'\rangle )$ החזירה תשובה חיובית (שוב, מפני שהיא השלב הראשון בריצת $H'$ שכתוצאתו הוחלט להיכנס ללולאה אינסופית). אבל לפי ההגדרה של H, משמעות תשובה חיובית זאת היא ש־$H'$ עוצרת על הקלט $\langle H'\rangle$, וזו שוב סתירה.

לא הבנתי מי אמר שאפשר לבנות את H' באופן שהיא תוכל לקרוא את התוצאה של עצמה, באופן שאפשר להוכיח שאם היא עוצרת על H' סימן שH החזירה תשובה חיובית וזה סימן שH' לא עצרה. אולי אם תיצור אלגוריתם שאם הוא מקבל את התוצאה של עצמו הוא נכנס ללולאה אינסופית, עדיין אני יכול ליצור אלגוריתם אחר שמזהה את המצב הזה ונותן תשובה שלילית. --195.60.234.6 13:45, 30 בינואר 2019 (IST)

ולמה לא מוכיחים לא בשלילה, בהנחה שאם נרצה לבנות מכונה שעל כל קלט תדע אם היא שייכת לR או לא, היא תצטרך להכיר אינסוף קלטים, שהרי מכונה שלא עוצרת הקידוד שלה הוא באורך אינסופי. ומאחר שכדי לבדוק אם המכונה עוצר או לא צריך לדעת את הקידוד שלה, ואי אפשר לעצור על קידוד אינסופי, ממילא אי אפשר לבנות שום מכונה שתעצור בכל קלט שהוא. אלא אם כן יש לה מספר סופי של קלטים שהיא מקבלת ודוחה. --195.60.234.6 13:51, 30 בינואר 2019 (IST)

קראתי במקום אחר, שחלק מההוכחה בנויה על כך שכל מכונה יכולה להחזיר את הקידוד של עצמה, ולכן אפשר לבנות מכונה שהקידוד שלה הוא H' על H' וכך נגיע לסתירה. על השאלה השניה, ראיתי כעת בפרק שפות לא רגולריות בספר על אוטומטים ושפות פורמליות, שיש אפשרות לשפה כריעה אפילו שאינה רגולרית ואין סוף למספר המילים שבה.--213.8.151.212 09:22, 31 בינואר 2019 (IST)