בתשובה לראובן, 14/12/06 11:08
בעית העצירה 424465
נכון. תראה; כל אלגוריתם סופי מייצר איזושהי סדרה אינסופית. אבל יש יותר סדרות אינסופיות מאלגוריתמים (או סדרות) סופיים‏1. אז מן הסתם יש סדרות אינסופיות ששום אלגוריתם סופי לא מייצר אותם. פשוט אין מספיק אלגוריתמים לייצר את כולן.

1 שגם זה משפט מעניין עם הוכחה משעשעת.
בעית העצירה 424468
תודה לכל מנחמי בכתב ובעלפה, אחרי שכתבתי את התגובה הבנתי שבעצם הסופיות של אורך האלגוריתם מכתיב גם את המספר הסופי של הסדרות שאפשר לייצר.
האם סדרות אלו הן לא דוגמאות טריוויאליות ל"מה מחשב לא יכול לעשות"? בלי צורך ברקורסיות והפניה עצמית?
בעית העצירה 424476
יש הרבה סדרות אינסופיות שאלגוריתם סופי יכול לייצר בצורה מאוד מוצלחת. פי, למשל, הוא מספר באורך אינסופי שלעולם אינו חוזר על עצמו ויש אלגוריתמים סופיים ידועים שמייצרים אותו. אז אפשר לייצר סדרות אינסופיות על-ידי אלגוריתם אינסופי; פשוט לא את כולן, אלא רק מספר די מצומצם (בן-מניה) מהן.
בעית העצירה 424477
זה מה שאמרתי. אבל מכאן נובע שיש אין סוף סדרות אינסופיות ש*אף* אלגוריתמם סופי לא יכול לייצר. מה נטפלו כולם לבעית העצירה?
בעית העצירה 424479
בעית העצירה אמנם ניתנת לקידוד כסדרה אינסופית, אבל היא מאוד-מאוד מעניינת בפני עצמה. נטפלו אליה כי היא אומרת הרבה על הבנה של מכונות-טיורינג את עצמן, לא בגלל שהיא סדרה אינסופית.
בעית העצירה 424489
לא יודע, גדי מציג את זה במאמר כ"נקודת חולשה" של המחשב, לא כ"עוד בעיה מעניינת". אם מישהו היה כותב מאמר כזה ואומר: המחשב לא יכול לייצר יותר ממספר בן מניה של סדרות אינסופיות‏1, לא נראה לי שמישהו היה קופץ ואומר "אבל בני אדם כן, לכן מותר האדם".

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

1 עוד דוגמה: סדרה אינסופית של אפס או אחד עבור כל משפט מתמטי, אם הוא נכון או לא.
בעית העצירה 424499
כלומר בעצם הכותרת המתאימה למאמר יכ[ו]לה [היתה] להיות
"לא מסובך להראות שיש רק מעט דברים שמחשב כן יודע לעשות.
מבין כל הדברים שמחשב לא יכול לעשות, הנה אחד, שהוא די מגניב".
בעית העצירה 424502
הממם.

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

אז מה מייחד דווקא את משפט טיורינג? יש לי הרגשה שהוא בכל-זאת די יחודי; לגבי הדוגמה הנוספת שהבאתי בתגובה 424494 (משפט גדל, בעצם), אני חושב שהוכחה שלה ממילא דומה מאוד ל(או בכלל מתבססת על) משפט טיורינג. אתה יכול לחשוב על עוד כאלה? אני לא יכול כרגע.
בעית העצירה 424504
לחשוב על עוד דוגמאות למה? אגב, אם כבר, משפט טיורינג מבוסס על גדל, לא?
בעית העצירה 424508
לא. אין צורך במשפט גדל כדי להראות שבעיית העצירה לא כריעה. מה שכן אפשר לומר הוא שאלמלא משפט גדל, ייתכן שטיורינג לא היה מוכיח את המשפט בזמן ובמקום שבו הוכיח אותו.
בעית העצירה 424509
כן, לזה התכוונתי.
בעית העצירה 424505
הדוגמה הנוספת קצת בעייתית. מה זה "נכון"? האם השערת הרצף נכונה או לא?
בעית העצירה 424528
אז תן שתי סדרות: "נובע מאקסיומות שנכון" "נובע מאקסיומות שלא נכון".
בעית העצירה 424555
אני כמובן מנטפק בצורה מופרזת, אבל גם במקרה הזה, זה לא משפט גדל כל עוד אין לך מערכת מסויימת של אקסיומות. הנקודה שלי היא שאני דווקא לא בטוח שכל זה נובע בקלות מבעיית העצירה.
בעית העצירה 424560
אני לא בטוח שהבנתי מה אמרת עכשיו, אבל בגדול: בהנתן סט אקסיומות, בנה מ"ט A שמקבלת כקלט משפט ועוברת על כל ההוכחות האפשריות, ועוצרת כשהיא מוצאת הוכחה למשפט. אם יש לך מכונה B שפותרת את בעית העצירה, עבור משפט-משפט וענה "כן" אם A עוצרת על המשפט ו"לא" אם לאו. הרץ את אותו אלגוריתם גם על שלילות המשפטים והנה לך שתי הסדרות.
בעית העצירה 424561
זה כנראה אני שלא מבין לאן אתה חותר. אני פשוט רציתי לציין שהבעיה של קביעה האם משפט הוא יכיח או לא היא לא תמיד בלתי ניתנת לפתרון; יש מערכות של אקסיומות שהן שלמות ונאותות.
בעית העצירה 424566
רציתי לומר שאני לא רואה שום סדרה אינסופית ''מעניינת'' בלתי-ניתנת-לחישוב שהיא לא בעיית העצירה או ניתנת לרדוקציה ממנה, כתגובה לביקורת של ראובן על נושא המאמר. נתתי דוגמה לסדרה אינסופית מעניינת כזו (האם משפט נכון או לא) אבל שניתנת לרדוקציה מבעיית העצירה. אם סדרה היא ממש ניתנת לחישוב, ודאי שהיא לא מתחרה עם בעית העצירה על נושא המאמר.
בעית העצירה 424481
לראות מקרה קונקרטי משכנע יותר מדיבורים באוויר על הבדלי עוצמות. יותר מזה - זה מאפשר לראות שקיימת בעיה *מעניינת* שאנחנו לא יכולים לפתור.
בעית העצירה 424491
לו'ידע. למשל, דמיין לעצמך עולם אלטרנטיבי שבו בעית העצירה דווקא כן שייכת לקבוצה בת-המניה של סדרות אינסופיות שיש מ''ט שמייצרת אותן. השוס של טיורינג היה שהוא הוכיח שבעית העצירה שייכת לקבוצה השניה בחלוקה של כן-ניתנות-ליצור לעומת לא-ניתנות ליצור, ולא בעצם זה שיש חלוקה כזו.
בעית העצירה 424493
זה לא מה שאמרתי?
בעית העצירה 424497
כן? חשבתי שהתכוונת באופן כללי שאולי רק בעיות לא-מעניינות (איך שלא תגדיר את אלה) אי-אפשר לפתור.
בעית העצירה 424500
התכוונתי באופן כללי שכל עוד אנחנו לא מכירים בעיות מעניינות שאי אפשר לפתור, עלולים לפטור את כל העסק באמירת "נו, אז מה אם הוא לא יודע לפתור כל מני בעיות אזוטריות? הן לא מעניינות אף אחד!"

למרבה המזל, אנחנו מכירים הרבה כאלו, ובעיית העצירה היא רק אחת מהן. בעיה מקסימה אחרת היא זו של ה-Wang tiling שנראה שבאה מתחום שונה, והבעיה העשירית של הילברט, של פתרון משוואות דיופנטיות שגם היא לכאורה באה מתחום שונה לגמרי. וגם אלו הן רק קצה הקרחון.
בעית העצירה 424503
ספר, ספר!
בעית העצירה 424506
דוד הראל סיפר על Wang tiling, עוזי סיפר על המשוואות הדיופנטיות:

הבעיה העשירית של הילברט [ויקיפדיה]
בעית העצירה 424532
לא מוצא Wang tiling, אבל ברור שהמשוואות הדיופנטיות הן פשוט מקרה פרטי של בעית העצירה. בעית העצירה עדין נראית לי כמו בעיה מיוחדת (לכל הפחות, הברורה ביותר מתוך מחלקת בעיות שקולות).
בעית העצירה 424557
טוב, יש בויקיפדיה האנגלית:
ושווה גם להזכיר את משפט רייס:

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

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

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

כמובן שיש קשר בין משפט רייס ובעיית העצירה - מוכיחים אותו על ידי כך שעושים רדוקציה מבעיית העצירה לבעייה של בחינת התכונה הלא טריוויאלית.
בעית העצירה 424562
רייס בהנדסת תוכנה מסחרית זה ''עבור כל בעיה תכנותית, יש מימוש שבאמת אף-אחד לא יכול להבין''. שאל כל מתכנת.
בעית העצירה 424507
למרבה המזל?
בעית העצירה 424510
אחרת, על מה היה אפשר לכתוב מאמרים?
בעית העצירה 424511
אולי על רצון חופשי.

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

יש לי הרגשה שתיכף אני הולך (שוב) להתבייש בפינה כי השאלה תתברר כמטומטמת, אבל שיהיה.
בעית העצירה 424512
שאלה טובה דווקא, ואין לי תשובה. כשתגיע, אצטרף אלייך בפינה.
בעית העצירה 424610
האם יש אלוהים?
האם ניתן להכריע אם יש אלוהים?
האם ניתן להכריע אם ניתן להכריע אם יש אלוהים?
האם...
בעית העצירה 424596
תן לי דוגמא מפורטת של אחת.

(נאמר בהומור, למען הסר הספק).
בעית העצירה 424830
כלומר, לספק רצפט לסדרה אין סופית שאי אפשר לשחזר באמצעות מ"ט? אין בעיה- הטל מטבע אין סוף פעמים.
בעית העצירה 424981
נראה לי שנוצר קצת בלגן בנוגע לחשיבות של אי-כריעות בעית העצירה. אז ככה: יש הרבה בעיות(=סדרות ביטים) שאי אפשר להכריע, הבעיה היא שאת רובן גם אי אפשר לתאר (הטל מטבע זו לא תאור). בעית העצירה היא הדוגמא הראשונה של בעיה שניתנת לתאור אבל לא להכרעה.
בעית העצירה 424480
כשאתה אומר "אורך האלגוריתם", למה אתה מתכוון?
בעית העצירה 424484
מספר הביטים של מכונת הטיורינג שלה (+ הקלט).

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים