בתשובה לראובן, 14/12/06 12:42
בעית העצירה 424479
עדי סתיו • בתשובה לראובן יום ה', 14/12/2006, 12:46
בעית העצירה אמנם ניתנת לקידוד כסדרה אינסופית, אבל היא מאוד-מאוד מעניינת בפני עצמה. נטפלו אליה כי היא אומרת הרבה על הבנה של מכונות-טיורינג את עצמן, לא בגלל שהיא סדרה אינסופית.
בעית העצירה 424489
ראובן • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:02
לא יודע, גדי מציג את זה במאמר כ"נקודת חולשה" של המחשב, לא כ"עוד בעיה מעניינת". אם מישהו היה כותב מאמר כזה ואומר: המחשב לא יכול לייצר יותר ממספר בן מניה של סדרות אינסופיות‏1, לא נראה לי שמישהו היה קופץ ואומר "אבל בני אדם כן, לכן מותר האדם".

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

‏1 עוד דוגמה: סדרה אינסופית של אפס או אחד עבור כל משפט מתמטי, אם הוא נכון או לא.
בעית העצירה 424499
ראובן • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:17
כלומר בעצם הכותרת המתאימה למאמר יכ[ו]לה [היתה] להיות
"לא מסובך להראות שיש רק מעט דברים שמחשב כן יודע לעשות.
מבין כל הדברים שמחשב לא יכול לעשות, הנה אחד, שהוא די מגניב".
בעית העצירה 424502
עדי סתיו • בתשובה לראובן יום ה', 14/12/2006, 13:31
הממם.

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

אז מה מייחד דווקא את משפט טיורינג? יש לי הרגשה שהוא בכל-זאת די יחודי; לגבי הדוגמה הנוספת שהבאתי בתגובה 424494 (משפט גדל, בעצם), אני חושב שהוכחה שלה ממילא דומה מאוד ל(או בכלל מתבססת על) משפט טיורינג. אתה יכול לחשוב על עוד כאלה? אני לא יכול כרגע.
בעית העצירה 424504
ראובן • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:33
לחשוב על עוד דוגמאות למה? אגב, אם כבר, משפט טיורינג מבוסס על גדל, לא?
בעית העצירה 424508
גדי אלכסנדרוביץ' • בתשובה לראובן יום ה', 14/12/2006, 13:40
לא. אין צורך במשפט גדל כדי להראות שבעיית העצירה לא כריעה. מה שכן אפשר לומר הוא שאלמלא משפט גדל, ייתכן שטיורינג לא היה מוכיח את המשפט בזמן ובמקום שבו הוכיח אותו.
בעית העצירה 424509
ראובן • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 13:40
כן, לזה התכוונתי.
בעית העצירה 424505
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 13:34
הדוגמה הנוספת קצת בעייתית. מה זה "נכון"? האם השערת הרצף נכונה או לא?
בעית העצירה 424528
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 16:39
אז תן שתי סדרות: "נובע מאקסיומות שנכון" "נובע מאקסיומות שלא נכון".
בעית העצירה 424555
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 19:44
אני כמובן מנטפק בצורה מופרזת, אבל גם במקרה הזה, זה לא משפט גדל כל עוד אין לך מערכת מסויימת של אקסיומות. הנקודה שלי היא שאני דווקא לא בטוח שכל זה נובע בקלות מבעיית העצירה.
בעית העצירה 424560
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 19:59
אני לא בטוח שהבנתי מה אמרת עכשיו, אבל בגדול: בהנתן סט אקסיומות, בנה מ"ט A שמקבלת כקלט משפט ועוברת על כל ההוכחות האפשריות, ועוצרת כשהיא מוצאת הוכחה למשפט. אם יש לך מכונה B שפותרת את בעית העצירה, עבור משפט-משפט וענה "כן" אם A עוצרת על המשפט ו"לא" אם לאו. הרץ את אותו אלגוריתם גם על שלילות המשפטים והנה לך שתי הסדרות.
בעית העצירה 424561
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 20:03
זה כנראה אני שלא מבין לאן אתה חותר. אני פשוט רציתי לציין שהבעיה של קביעה האם משפט הוא יכיח או לא היא לא תמיד בלתי ניתנת לפתרון; יש מערכות של אקסיומות שהן שלמות ונאותות.
בעית העצירה 424566
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 20:15
רציתי לומר שאני לא רואה שום סדרה אינסופית ''מעניינת'' בלתי-ניתנת-לחישוב שהיא לא בעיית העצירה או ניתנת לרדוקציה ממנה, כתגובה לביקורת של ראובן על נושא המאמר. נתתי דוגמה לסדרה אינסופית מעניינת כזו (האם משפט נכון או לא) אבל שניתנת לרדוקציה מבעיית העצירה. אם סדרה היא ממש ניתנת לחישוב, ודאי שהיא לא מתחרה עם בעית העצירה על נושא המאמר.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות