בתשובה להאייל הצעיר, 07/01/07 17:44
 |
|
 |
||
|
||||
 |
אכן יש צורך בהנחה שאתה מתאר, אבל אם כבר, הייתי מתאר אותה כהנחה מאד רחבה (אגב, לא צריך להניח ש- B ממש "מריץ" את A. מספיק להניח שקיים מודל B ששקול להרצת A. לדוגמה, אם תיתן לי קוד שפותר את בעיית העצירה, אני יכול לשנות אותו במעט, ולאו דווקא לכתוב קוד חדש שמריץ אותו). לי נראה שמודל שלא מקיים אותה הוא מוגבל דיו על מנת שבכלל לא תהיה מוגדרת בו בעיית העצירה (כלומר, גם לא יהיו בו מכונות שמקבלות כקלט מכונות אחרות ואומרות עליהן משהו) אתה יכול לתת לי דוגמה למודל (כלשהו, אבל רצוי מעניין) שבו בעיית העצירה מוגדרת, אך ההנחה הזאת לא מתקיימת? |
 |
 |
 |
|
|
|
||
|
||||
|
אתה יכול לתת דוגמא למודל שבו בעית העצירה מוגדרת ואינו שקול למכונת טורינג? זה מזכיר לי משהו: ההוכחה של אי קיום מ"ט שפותרת את בעית העצירה היא מאד קצרה ואלגנטית, *אחרי שיודעים שיש מ"ט אוניברסלית*. גדי לא התעכב הרבה על הנקודה הזו: הפואנטה האמיתית היא קיום מ"ט אוניברסלית, כלומר שניתן לקדד מ"ט כך שניתן להריץ אותה על מ"ט אוניברסלית. יש כאן דימיון יפה למשפט אי-השלמות של גדל: גם שם ההוכחה עצמה היא קצרה ופשוטה אבל הנקודה העיקרית היא שאפשר לתאר את המושג "קיימת הוכחה" בעזרת השפה, ןזה הרבה יותר קשה וטכני. |
|
|
|
|
|
|
||
|
||||
|
הנה דוגמה: קבוצת המכונות שכוללת את כל מכונות הטיורינג, ועוד מכונת קסם אחת שפותרת את בעיית העצירה עבור המכונות בקבוצה. חוץ מזה, מה שאורי כתב מתחתיי על מכונת טיורינג אוניברסלית. |
|
|
|
|
|
|
||
|
||||
|
מעליך! | |
|
|
|
|
|
||
|
||||
|
יש צורך בתיקון (*) (טכני בעיקרו), אבל למעט העניין הזה אתה צודק. אפשר להיכנס לויכוח (עקר לדעתי) על עד כמה המודל הזה "מעניין", או עד כמה ההנחה צרה או רחבה, אבל אני מסכים עם ההערה של אורי (תגובה 428290, זו ש*מעליך*) שבסופו של דבר ההוכחה לא חוסכת הרבה, כי הסיבוך העיקרי יהיה במקום אחר (לא השתכנעתי שאוניברסליות היא תנאי הכרחי, אבל יש כנראה צורך בדרישה שניתן יהיה לקודד את המכונות שלנו על סרט קלט, שהיא מאד קרובה לזה). -------------- (*) הבעיה: כדי שבעיית העצירה תהיה מוגדרת על הקבוצה שהגדרת, צריכה להיות דרך להעביר את מכונת הקסם (מ"ק) שלך כקלט, לעצמה ולמכונות אחרות (אחרת לא ניתן לטעון ש"קיימת מכונה בקבוצה שמקבלת את כל המכונות אחרות בקבוצה וגו"' (יותר נכון, הטענה תהיה טריביאלית - שקרית במובן הריק), כי לא ניתן להעביר את מ"ק כקלט). הפתרון: הקבוצה תהיה מ"ט "רגילות" (ביטיות) שרצות על סרטי טריטים (0,1,X) ואשר הוסיפו לכולן לגרף המצבים שאם הן קוראות "X" מהקלט הן מדפיסות בגדול "מה X?????" ויוצאות מיד. מ"ק תעשה אותו הדבר אלא אם הקלט שלה הוא "X" (בלבד), ואז היא תתיחס לכך כאילו הקלט היה מ"ק (וכמובן תחזיר תשובה שהמכונה עוצרת, ללא תלות בקלט שלה). |
|
|
|
|
|
|
||
|
||||
|
א. אורי כבר כתב "מעליך" מעליך. חוץ מזה, טעות, טעינו, טועים ושאלה יהיו הטעויות שלי. ב. כדי להגן על כבודי: חשבתי לפרט את ההערה (*) בתגובה שלי, אבל החלטתי שזה מיותר. ג. מכונה אוניברסלית היא לא תנאי הכרחי כדי *לנסח* את בעיית העצירה, אבל ה*הוכחה* של טיורינג מתבססת עליה. |
|
|
|
|
|
|
||
|
||||
|
א. לא התכוונתי לתקן אותך. התכוונתי לרמוז לתגובת ה"מעליך" של אורי, ששעשעה אותי בנחרצותה, ואשר ידעתי שתגובתי תתפרסם מתחתיה. צר לי אם זה התפרש אחרת. ג. אני לא יודע לנסח את התנאי ההכרחי והמספיק לתקפות ההוכחה, אבל אני לא חושב שתכונת האוניברסליות היא תנאי הכרחי (להוכחה, לא לניסוח בעיית העצירה). אני אציג דוגמא לעולם שבו לא קיימת מכונה אוניברסלית, אבל הוכחת בעית העצירה תקפה. לא חשבתי עליה הרבה, אז ייתכן שיש בה באגים. מסתכלים על מ"ט עם אורקל. האורקל יודע להחזיר למכונה שקוראת לו אחת מ- 3 תשובות: אם היא עוצרת תמיד, על כל קלט שניתן לה, הוא מחזיר 0. אם קיים קלט שעבורו היא לא עוצרת, הוא מחזיר 1. את שתי התשובות האלו הוא מחזיר רק אם לא קיים קלט שעבורו המכונה "לא קונסיסטנטית" (*). אחרת, האורקל מחזיר 2. בעולם הזה לא קיימת מ"ט אוניברסלית. זאת משום שהמכונה האוניבסרלית לא מסוגלת לסמלץ את האורקל (והאורקל שלה עצמה מחזיר לה 1, כי יש קלטים שעבורם היא לא עוצרת). דוגמה למכונה שלא ניתן לסמלץ: מכונה שקוראת לאורקל, מדפיסה את התשובה ומשם ממשיכה לעשות משהו אחר. מצד שני, קיימת מכונה "כמעט אוניברסלית" שמסמלצת מ"ט, ואם הן קוראות לאורקל היא מחזירה להן 2. מכונה כזאת, שרצה על תת-מכונה, עוצרת אמ"מ תת המכונה עוצרת, למרות שהיא לא מסמלצת את פעולתה באופן מלא. ------------ (*) ב"לא קונסיסטנטית" הכוונה היא שהשאלה אם המכונה תעצור או לא תלויה בקלט שהיא מקבלת מהאורקל - 0, 1 או 2. כלומר, אם קיים קלט שעבורו, נניח, היא עוצרת אם היא מקבלת 0 ולא עוצרת אם היא מקבלת 2 - האורקל יחזיר לה 2 (לכל קלט). |
|
|
|
|
|
|
||
|
||||
|
אמנם, אורקל זה בעיקר עניין של הגדרה, אבל ההגדרה שאני מכיר לא דורשת שניתן יהיה לסמלץ את האורקל (ובפרט, אורקל יכול להיות גם לשפות לא כריעות). | |
|
|
|
|
|
||
|
||||
|
למיטב הבנתי, בעולם שבו קיימים אורקלים, אם מכונה אוניברסלית עושה אמולציה למכונה אחרת, וזו קוראת לאורקל במהלך האמולציה - על המכונה האוניברסלית להחזיר לה את התשובה שהאורקל היה מחזיר לה. לצורך כך מותר לה כמובן להשתמש באורקל שלה עצמה, אבל לא באורקל של המכונה המורצת, שאליו אין לה גישה. אני יכול לחשוב על שתי הגדרות אלטרנטיביות של אורקל או של מכונה אוניברסלית שיפגמו בטיעון הנ"ל: הראשונה - שאורקל לא מוגדר עבור מכונה מסוימת, אלא קיים בעולם אורקל שכל מכונה יכולה לפנות אליו עם קלט, והוא יחזיר לה את הפלט. השניה - שהאורקל הוא כן ספציפי לכל מכונה, אבל ממכונה אוניברסלית לא נדרש לסמלץ את האורקל של המכונה המורצת, אלא היא מקבלת גישה לאורקל של המכונה המורצת. אני התיחסתי למקרה שבו לכל מכונה יש אורקל אחר (או, לחליפין, שהאורקל מקבל כקלט את המכונה שקוראת לו, ואין למכונה אפשרות להחליף לו את הקלט). ייתכן שיש לקרוא ליצור כזה בשם אחר (שנורקל?), אבל בהנתן ההגדרה הזאת, אכן בעולם שהגדרתי אין מכונה אוניברסלית, ואולם ההוכחה של בעיית העצירה תקפה. בכל מקרה כמובן שאני לא דורש מאורקל שניתן יהיה לסמלץ אותו, אחרת אין בו צורך. |
|
|
|
|
|
|
||
|
||||
|
אני חשבתי דווקא על כך שיש אורקל אחד קבוע "ברקע", וגם למכונה האוניברסלית יש גישה אליו. אני מסכים שאם האורקל הוא שונה לכל מכונה אז כנראה שאין מכונה אוניברסלית - אבל לדעתי אנחנו נתקעים כבר ברמת ההגדרה. נניח שאני מכונה אוניברסלית. אני מקבל כקלט קידוד של מכונת טיורינג וקלט עבורה. עכשיו, איך אני מבדיל בין מכונת טיורינג A שיש לה אורקל K, ובין *אותה* מכונת טיורינג A רק עם אורקל שונה, T? (כלומר, ההבדל היחיד הוא בתשובות שהאורקל יחזיר, לא בהתנהגות של A כתלות בתשובות הללו). אני חייב לקודד את ההבדל בין K ו-T כחלק מהקלט, אבל כאן אני נתקע; יש אורקל לכל שפה, אבל מספר השפות הוא לא בן מניה, ואם אני מסוגל לקודד משהו כקלט למכונת טיורינג, הוא מן הסתם שייך לקבוצה בת מניה (קבוצת כל הקידודים). |
|
|
|
|
|
|
||
|
||||
|
בדוגמה שאני נתתי, יש אורקל שונה לכל מכונה, אבל לכל מכונה יש אורקל יחיד. לא קיימות שתי מכונות, שהן אותה מכונה עם אורקלים שונים. לצורך העניין, אפשר להגדיר שקיים אורקל קבוע ברקע, אבל הוא מקבל כקלט את המכונה שניגשת אליו, ולמכונה אין אפשרות לשנות את הקלט הזה. ייתכן שזה לא מודל סנטדרטי (ואתה מוזמן לקרוא לאורקל הזה בשם אחר), אבל הוא מוגדר היטב, והבעיה שאתה מציין לא קיימת בו. | |
|
|
|
|
|
||
|
||||
|
זה אכן מודל לא סטנדרטי, ולטעמי הוא גם די מוזר ומלאכותי (אורקל שמתנהג באופן שונה בהתבסס על המכונה שקוראת לו?) אבל על פניו אני אכן לא רואה איתו בעיה עקרונית. | |
|
|
|
|
|
||
|
||||
|
פתחתי את הדיון הזה בכך שניסיתי להגיד שאת ההוכחה לבעיית העצירה ניתן להכליל כך שתחול לא רק על מכונות טיורינג, אלא על מודלים כלליים יותר. בהמשך הדיון הוברר שעדיין צריך להניח הנחות מסוימות על המודל. ניסיתי להפריך את הטענה שקיום מכונה אוניברסלית היא תנאי הכרחי לצורך ההוכחה, ולכן הבאתי מודל מאד מוזר, שכל מטרתו להוכיח את זה. כעת נשאלת השאלה האם ניתן לנסח תנאי יותר חלש מקיום מכונה אוניברסלית (למשל קיום מכונה ''כמעט אוניברסלית'', שזו מכונה שעוצרת אמ''מ המכונה שהיא קיבלה כקלט עוצרת על הקלט שלה), שיספיק על מנת שהוכחה תהיה תקפה לכל מודל שמקיים אותו. שאלה נוספת היא האם קיים מודל מעניין שאין בו מכונה אוניברסלית אבל יש בו מכונה כמעט אוניברסלית (או שמקיים את התנאי החלש יותר, אם מנסחים אותו באופן אחר). |
|
|
|
|
|
|
||
|
||||
|
קצת הלכתי לאיבוד, אז אולי תוכל להחזיר אותי חזרה לתמונה - תוכיח לי שבמודל שהצעת כרגע בעיית העצירה לא פתירה. | |
|
|
|
|
|
||
|
||||
|
תוותר לי על המשקל והחריזה, נכון? נניח שקיימת מכונה P שמקבלת כקלט מכונה M וקלט x ומחזירה האם M עוצרת על x (לכל M ולכל x). נבנה 3 מכונות כמעט אוניברסליות Q0,Q1,Q2, שכל אחת מהן מקבלת כקלט מכונה Q ומריצה את P על הקלט M=Q, x=Q. לאחר מכן, אם P מחזירה "M עוצרת על x" אז היא נתקעת, אחרת היא עוצרת. ההבדל ביניהן הוא שאם במהלך הסימולציה P פונה לאורקל שלה, כל אחת מהן מחזירה לה משהו אחר: Qi מחזירה לה i. מכיוון שלכל מכונה, התשובה של האורקל לאותה המכונה לא תלויה בקלט אלא רק במכונה, נובע שאחת המכונות האלו (לפחות) תסמלץ את P נאמנה (כי P תקבל בדיוק את הקלט שהאורקל היה מעביר לה) (*). נניח שזו Qi. כלומר, Qi היא מכונה שמקבלת כקלט מכונה Q ועוצרת אמ"מ Q לא עוצרת על הקלט Q. כעת נריץ את Qi על הקלט Qi, ואידך זיל גמור. אגב, שים לב ש- Qi כלל לא קוראת לאורקל של עצמה, ולכן זה לא משנה מה הוא היה מחזיר. ------------------- (*) בהתחלה חשבתי שבכל מקרה Q2 מסמלצת את P נאמנה (לפחות, מספיק נאמנה כך שההוכחה תהיה תקפה). זאת משום שאם P לא קונסיסטנטית אז ממילא היא מקבלת 2 מהאורקל, ואם היא כן קונסיסטנטית, אז לא משנה מה היא מקבלת מהאורקל. העניין הוא שה"לא משנה" הזה מדבר רק על השאלה האם P תעצור, לא על השאלה איזה קלט היא תחזיר. לכן צריך להגדיר 3 מכונות "כמעט אוניברסליות", ולא אחת. אגב, אם אנחנו יודעים מראש שהמכונה P עוצרת על כל קלט אז בכל זאת מספיק להגדיר מכונה אחת - זו שמחזירה ל- P (כשהיא קואת לאורקל) את התשובה "מכונה זו עוצרת תמיד". |
|
|
|
|
|
|
||
|
||||
|
עכשיו אני ממש מבולבל. מה זה "אורקל" בשבילך? בשבילי אורקל הוא קופסה שחורה שמכריעה שפות - שואלים אותה על מילה והיא עונה "כן" אם המילה בשפה ו"לא" אם לא. ממה שכתבת כאן אני מקבל את הרושם שאתה תופס אורקל (לפחות בהקשר הזה) בתור משהו שיכול לענות רק תשובה אחת, שוב ושוב. מה שזה בעצם אומר הוא שכל מכונת טיורינג מגיעה עם עוד "ביט מידע חבוי" (שני ביטים, בעצם, כי יכולים להיות שלושה ערכים) שאינו חלק מהקידוד שלה ורק לה יש גישה אליו. | |
|
|
|
|
|
||
|
||||
|
האורקל הזה הוא קופסה שחורה ששואלים אותה על מילה והיא עונה אחד מ- 3 ערכים. העניין הוא שבמודל הזה המכונה שניגשת לאורקל חייבת לתת כקלט לאורקל את עצמה. זה שקול לכך שכל מכונה מגיעה עם עוד טריט מידע חבוי, שאינו חלק מהקידוד שלה (אם כי מוגדר חד ערכית ע"י הקידוד שלה) ושרק לה יש גישה אליו. | |
|
|
|
|
|
||
|
||||
|
טוב ויפה, אבל בוא נניח שעל קלט כלשהו P פונה לאורקל שלה פעמיים כדי לבדוק שתי מילים שונות, והוא מחזיר לה פעם 0 ופעם 1. אף אחת משלוש המכונות שהצעת לא מסמלצת את ההתנהגות הזו. (אם הכוונה שלך היא "המכונה יכולה לשאול את האורקל אך ורק על מילה בודדת - המילה שמייצגת אותה עצמה" - אז כאמור, אין צורך בדיבורים על אורקל ומספיק לדבר על ביט חבוי). |
|
|
|
|
|
|
||
|
||||
|
אתה צודק בהחלט. הגדרתי את האורקל כך בדיוק כדי שאכן אחת משלוש המכונות תסמלץ את ההתנהגות. למעשה, כמו שאתה מציין - ביט חבוי הוא תיאור פחות עקום, והוא אפילו מרשה קיום של שתי מכונות זהות עם ביט חבוי שונה: מהסיבה שאתה אמרת לפני כמה תגובות לא קיימת מכונה אוניברסלית למודל כזה (היא לא תדע להבדיל בין המכונות הזהות עם ביט חבוי שונה), אבל קיימות שתי מכונות כמעט אוניברסליות, כך שכל מכונה מסומלצת ע"י אחת מהן לפחות - וזה כבר מספיק כדי שההוכחה תהיה תקפה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |