בתשובה לעומר, 05/08/05 2:19
 |
|
 |
||
|
||||
 |
שלום, יש לי שאלה. אשמח לקבל תשובה אם מישהו יודע... האם הוכח שלא קיים אלגוריתם שבהינתן עיגול הוא מוצא ריבוע בעל שטח זהה לשטח הריבוע? כלומר האם זאת דוגמא לבעיה שהוכח שלא ניתן לפתור אותה בעזרת מחשב? או שבעצם הוכח רק שלא ניתן לפתור את הבעיה באמצעות סרגל ומחוגה, ובאופן תיאורטי עדיין יתכן שאפשר למצוא דרך אחרת לפתור את הבעיה? תודה, |
 |
 |
 |
|
|
|
||
|
||||
|
הוכח שלא ניתן לפתור את הבעיה באמצעות סרגל (לא מסומן) ומחוגה. אם תכניס לשימוש כלים "קסומים" כמו סרגל שמסומן עליו המרחק פאי, לדעתי לא תתקשה לרבע את המעגל. לדבר על "אלגוריתם" בהקשר הזה קצת יותר בעייתי - אלגוריתם שרץ על איזו מכונה? מכונות טיורינג ודומיהן הן דיסקרטיות, וכדי ליצור (בצורה "מדוייקת") את ריבוע המעגל צריך משהו רציף. |
|
|
|
|
|
|
||
|
||||
|
מעגל אפשר לסמן בעזרת משוואה (דיסרטית) או באמצעות הפרמטרים (הדיסקרטיים) שלו. | |
|
|
|
|
|
||
|
||||
|
כן, בקריאה חוזרת מה שכתבתי נשמע די מקושקש. מה שהתכוונתי לומר הוא שלפני שמדברים על אלגוריתם, צריך להגדיר במדוייק מה בעצם אנחנו מקבלים בתור ''ריבוע מעגל חוקי''. | |
|
|
|
|
|
||
|
||||
|
קלט, שלושה פרמטרים שמציינים את המעגל: הרדיוס, המרחק של נקודת המרכז מראשית הצירים בכיוון הציר האופקי, והמרחק של נקודת המרכז מראשית הצירים בכיוון הציר האנכי. פלט: שלושה מספרים שמציינים ריבוע בעל שטח זהה לשטח הקלט: אורך הצלע, והמרחק של המרכז מראשית הצירים. פיתרון: עבור רדיוס מסויים, ומיקום מסויים, נחזיר אורך שלע של שורש פאי כפול הרדיוס, ושני אפסים. הצלחתי לרבע את המעגל. |
|
|
|
|
|
|
||
|
||||
|
הדגמת יפה את הבעייתיות של הסיטואציה שבה לא מגדירים במדויק על איזו מכונה רץ האלגוריתם. אפשר לפתור את בעית העצירה בצורה דומה: פשוט מחזירים "כן" אם המכונה עוצרת על הקלט שקיבלנו ו"לא" אם היא לא. במקרה הנוכחי שלנו, לא התייחסת לשאלת הייצוג - כיצד אתה מייצג "מספר" במחשב? אם יש לך קידוד מיוחד עבור "פאי" ועבור "שורש", והמעגל שלך הוא בעל קוארדינטות ניתנות לייצוג (נניח - מספרים שלמים), אז כן, פתרת את הבעיה, בעזרת כלי שדי דומה ל"סרגל שעליו מסומן פאי". |
|
|
|
|
|
|
||
|
||||
|
מספר יכול להיות מחרוזת שמתארת את המספר. למשל "1", "אחד", "1.0" ועוד. בצורה כזאת, גם "שורש פאי כפול <מספר>" הוא מספר לגיטימי. | |
|
|
|
|
|
||
|
||||
|
מקובל, אז יש לנו סרגל קסום. אגב, בצורה הזו גם "המספר הטבעי הקטן ביותר שאינו ניתן לתיאור בפחות ממאה מילים" נחשב "מספר". (ועוד הערה שמתקשרת לניג'וס שלי מתגובה 398538: גם בשיטת הייצוג הזו נצליח לייצג רק אוסף זניח של מספרים. למרבה המזל, פאי הוא המספר היחיד, בנוסף למספרים השלמים, שצריך לייצג כדי לרבע את המעגל). |
|
|
|
|
|
|
||
|
||||
|
האוסף הזניח הזה מכיל את כל המספרים המעניינים (מספר מעניין = מספר שמישהו חשב שהוא מספיק מעניין על מנת להמציא לו ייצוג). | |
|
|
|
|
|
||
|
||||
|
אין מספר כזה, הרגע תיארת אותו בעשר מלים. | |
|
|
|
|
|
||
|
||||
|
בדיוק. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |