בתשובה לתוהה, 15/12/06 22:59
Reset 424715
קהלת • בתשובה לתוהה יום ו', 15/12/2006, 23:31
רצית - קיבלת.
האלגוריתמים שלי מכיל משוואה דיופונטית פולינומיאלית ומחפש לה פיתרון בטבעיים ע''י השיטה המתוחכמת של ניחוש לא סדור. יכול להיות שימצא פתרון, יכול להיות שלא, בשום שלב לא ניתן להגיד שלא קיים פתרון (כי יש עוד מספרים שלא ניסינו). אם קיים אלגוריתם המסוגל לקבוע האם התוכנה עוצרת, אזי הוא פתר את השאלה האם קיים פתרון בטבעיים עבור המשוואה הנתונה, מה שסותר הוכחה הרבה יותר ''מתמטית'' מבחינתך (כבר קישרו אליה בדיון הזה), הבעיה העשירית של הילברט.
Reset 424717
גדי אלכסנדרוביץ' • בתשובה לקהלת יום ו', 15/12/2006, 23:46
הבעיה האהובה עלי היא וריאציה על Wang tiling - נניח שיש לנו אוסף כלשהו של אבני כמו-טטריס (כלומר, כמו האבנים שיש בטטריס אבל יכולות להיות מכל גודל שהוא, לא רק 4), האם ניתן לרצף את המישור כולו באמצעות עותקים של איברים מהאוסף?

מתברר שגם אלגוריתם כללי לפתרון הבעיה הזו לא קיים.

(הרחבה על מה זה לעזאזל "אבן כמו-טטריס" - Polyomino [Wikipedia])
Reset 424807
קהלת • בתשובה לגדי אלכסנדרוביץ' יום א', 17/12/2006, 0:42
במבט ראשון נדמה לי שאפשר לחלק את הבעיה לשני חלקים:
שיטה ראשונה לריצוף המישור - צור צורה הניתנת לגיבוש ‏1 באמצעות אבנים מהאוסף. אני מניח שבהינתן אוסף סופי של צורות אפשר להסיק האם קיימת צורה כזו (רק מניח, אין לי באמת את הכלים המתמטיים להתמודד עם הבעיה). אבל בעצם מי מבטיח לי שצורה אחת מספיקה, אולי דרושות כמה צורות כדי למלא את כל החללים (כמו כדורגל) ? היות ובניגוד לצורה הראשונה אנחנו לא מחפשים מינימום מחזורי, אין שום סיבה לשים מגבלה על הגודל, מה שגורם לי לחפש מחזור שיכול להיות אינסופי (זה עלול לקחת קצת זמן).
שיטה שניה - מצא שיטה (או אולי לפעמים אפילו אין שיטה מסודרת) להמשיך להרכיב עוד ועוד צורות בלי רווחים עד אינסוף. אני מניח שכאן לב הבעיה.

אתה יכול לקשר לסקיצה של ההוכחה ?

‏1 שאפשר להמשיך אותה מכל צדדיה ביחידות חוזרניות מבלי להשאיר רווחים.

[אילו היו חמש דקות של נסיון להתמודד עם בעיה שאין לי את הכלים להתמודד איתה]
Reset 424823
גדי אלכסנדרוביץ' • בתשובה לקהלת יום א', 17/12/2006, 8:18
אני לא בטוח מה אתה מנסה לעשות - לי זה נראה כאילו אתה מנסה דווקא לפתור את הבעיה. אם אתה מנסה להוכיח שהיא לא פתירה דרך גישת "בואו ננסה לפתור ונראה איפה אנחנו נתקעים", זו לא הדרך הנכונה.

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

אני לא מכיר מקום באינטרנט שאפשר לראות בו את ההוכחה שאי אפשר להכריע את בעיית הריצוף עם Wang tile. ההוכחה המקורית היא ב:

Berger, R. (1966). "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66(1966).

והרעיון הוא רדוקציה מבעיית הכרעה במכונות טיורינג (אם איני טועה, ממש מבעיית העצירה עצמה). אם היא זמינה לך, אתה יכול גם להעיף מבט בחוברת של קורס החישוביות של הטכניון, שנכתבה על ידי עודד גולדרייך - הוא מדגים שם משהו כמעט זהה.
Reset 424858
קהלת • בתשובה לגדי אלכסנדרוביץ' יום א', 17/12/2006, 11:45
נדמה לי שהם מרחיקים טיפה מעבר לבעיה שהגדרת, אבל העקרון דומה.
Reset 424719
תוהה • בתשובה לקהלת שבת, 16/12/2006, 0:24
ואולי יהיה לך אלגוריתם שידע להגיד כן/לא בכל מקרה שניתן לכתוב אלגוריתם, ו"אני לא יכול לדעת" במקרים האחרים?
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות