בתשובה לגדי אלכסנדרוביץ', 14/12/06 12:48
בעית העצירה 424491
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 13:08
לו'ידע. למשל, דמיין לעצמך עולם אלטרנטיבי שבו בעית העצירה דווקא כן שייכת לקבוצה בת-המניה של סדרות אינסופיות שיש מ''ט שמייצרת אותן. השוס של טיורינג היה שהוא הוכיח שבעית העצירה שייכת לקבוצה השניה בחלוקה של כן-ניתנות-ליצור לעומת לא-ניתנות ליצור, ולא בעצם זה שיש חלוקה כזו.
בעית העצירה 424493
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:11
זה לא מה שאמרתי?
בעית העצירה 424497
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 13:15
כן? חשבתי שהתכוונת באופן כללי שאולי רק בעיות לא-מעניינות (איך שלא תגדיר את אלה) אי-אפשר לפתור.
בעית העצירה 424500
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:20
התכוונתי באופן כללי שכל עוד אנחנו לא מכירים בעיות מעניינות שאי אפשר לפתור, עלולים לפטור את כל העסק באמירת "נו, אז מה אם הוא לא יודע לפתור כל מני בעיות אזוטריות? הן לא מעניינות אף אחד!"

למרבה המזל, אנחנו מכירים הרבה כאלו, ובעיית העצירה היא רק אחת מהן. בעיה מקסימה אחרת היא זו של ה-Wang tiling שנראה שבאה מתחום שונה, והבעיה העשירית של הילברט, של פתרון משוואות דיופנטיות שגם היא לכאורה באה מתחום שונה לגמרי. וגם אלו הן רק קצה הקרחון.
בעית העצירה 424503
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 13:31
ספר, ספר!
בעית העצירה 424506
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:36
דוד הראל סיפר על Wang tiling, עוזי סיפר על המשוואות הדיופנטיות:

הבעיה העשירית של הילברט [ויקיפדיה]
בעית העצירה 424532
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 16:50
לא מוצא Wang tiling, אבל ברור שהמשוואות הדיופנטיות הן פשוט מקרה פרטי של בעית העצירה. בעית העצירה עדין נראית לי כמו בעיה מיוחדת (לכל הפחות, הברורה ביותר מתוך מחלקת בעיות שקולות).
בעית העצירה 424557
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 19:51
טוב, יש בויקיפדיה האנגלית:
ושווה גם להזכיר את משפט רייס:

משפט רייס [ויקיפדיה]

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

למה בעיית העצירה היא לא בדיוק מקרה פרטי של זה? כי הקלט בבעיית העצירה הוא מכונה וקלט כלשהו שעליו היא מורצת. במשפט רייס הקלט הוא רק המכונה.

כמובן שיש קשר בין משפט רייס ובעיית העצירה - מוכיחים אותו על ידי כך שעושים רדוקציה מבעיית העצירה לבעייה של בחינת התכונה הלא טריוויאלית.
בעית העצירה 424562
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 20:03
רייס בהנדסת תוכנה מסחרית זה ''עבור כל בעיה תכנותית, יש מימוש שבאמת אף-אחד לא יכול להבין''. שאל כל מתכנת.
בעית העצירה 424507
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 13:37
למרבה המזל?
בעית העצירה 424510
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ה', 14/12/2006, 13:41
אחרת, על מה היה אפשר לכתוב מאמרים?
בעית העצירה 424511
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 14:01
אולי על רצון חופשי.

אבל עוררת אצלי שאלה: הראית שבעיית העצירה אינה פתירה ע"י מכונת טיורינג, ועל-ידי כך פתרת את המטא-בעיה ששואלת אם בעיית העצירה ניתנת לפתרון. בכך יצרת היררכיה בת שתי רמות, בה הרמה השניה פתורה (והיא אומרת שאי אפשר לפתור את הראשונה.) כן? יש דוגמאות ידועות לשאלות שרק ברמה השלישית (או גבוהה יותר) מקבלות תשובה, אם בכלל?

יש לי הרגשה שתיכף אני הולך (שוב) להתבייש בפינה כי השאלה תתברר כמטומטמת, אבל שיהיה.
בעית העצירה 424512
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ה', 14/12/2006, 14:05
שאלה טובה דווקא, ואין לי תשובה. כשתגיע, אצטרף אלייך בפינה.
בעית העצירה 424610
אביב י. • בתשובה לשוטה הכפר הגלובלי יום ו', 15/12/2006, 1:13
האם יש אלוהים?
האם ניתן להכריע אם יש אלוהים?
האם ניתן להכריע אם ניתן להכריע אם יש אלוהים?
האם...
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות