בתשובה לארז ליבנה, 23/02/04 14:06
התיזה של צ'רץ'-טיורינג 199734
דה-קארט • בתשובה לארז ליבנה יום ב', 23/2/2004, 15:17
זה כמובן תלוי באיך אתה מגדיר *אלגוריתם*. כל הגדרה סבירה תהיה משהוא בסגנון הבא: מכונה המאפשרת לחשב את הערך (=פלט) של פונקציה מתמטית מסויימת, על קלט X כלשהוא, באמצעות הפעלת סדרת פעולות לפי סט כללים קבוע וסופי (מסובך ככל שיהיה). מן הסתם אתה תרשה לאלג' להשתמש בזיכרון (אולי אפילו אינסופי).

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

‏1 תחת ההנחות שציין אלון. וניתן להסיר אותן במאמץ קטן.
התיזה של צ'רץ'-טיורינג 199753
גדי אלכסנדרוביץ' • בתשובה לדה-קארט יום ב', 23/2/2004, 16:17
תוכל לתת כמה דוגמאות של הפונקציות הללו, או שרק הוכח הקיום שלהן אבל לא מצאו דוגמא? (אני חושב שאני זוכר במעורפל ששמעתי משהו על שימוש במשפט קנטור על קבוצת השפות הפורמליות או משהו בסגנון. צריך ללמוד את זה באמת)
התיזה של צ'רץ'-טיורינג 199769
דה-קארט • בתשובה לגדי אלכסנדרוביץ' יום ב', 23/2/2004, 16:58
המינוח המדוייק שצריך להשתמש בו הוא שפות בלתי כריעות (השתמשתי במונח פונקציות רק לצורך הבהרה). מצאו כמה כאלו, אבל הדוגמא היחידה שאני זוכר זו בעית העצירה‏1.
הקיום של הרבה שפות בלתי כריעות כאלו נובע בפשטות מכך שיש הרבה יותר שפות (שתיים בחזקת ALEF EFES) מאשר אלגוריתמים (ALEF EFES).
_________
‏1 בהינתן מכונת טורינג M וקלט מסויים עבורה X, החלט האם M תסיים את ריצתה על X בזמן סופי או לא (בשפת העם, תיכנס ללולאה אינסופית).
התיזה של צ'רץ'-טיורינג 199775
עוזי ו. • בתשובה לדה-קארט יום ב', 23/2/2004, 17:13
קצת מוזר שמכל הטקסט הזה, את שתי המלים הכי-עבריות החלטת לשעתק: ALEF זה אלף, EFES זה אפס.
נכון 199787
דה-קארט • בתשובה לעוזי ו. יום ב', 23/2/2004, 19:06
אני הייתי נזהר לגבי הניסוח הזה של תזת צ'רצ'-טורינג 200125
כליל החורש נאורי • בתשובה לדה-קארט יום ג', 24/2/2004, 16:31
ראה, למשל:
אני הייתי נזהר לגבי הניסוח הזה של תזת צ'רצ'-טורינג 200160
דה-קארט • בתשובה לכליל החורש נאורי יום ג', 24/2/2004, 18:20
תודה. הנושא של fair non-determinism נשמע מעניין מאוד. שאר המודלים האלטרנטיביים מסתמכים באופן "כבד" על איזשהוא משאב אינסופי, ואז זה לא מאוד מפתיע שיש להם יותר כח (אני מקווה שלא יסתבר שגם ה-fair non-determinism מסתמך על משאב אין סופי).

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

____
‏1 "הנחה" זו עוד דוגמא לכפל משמעות הנהדר שיש בעברית בכמה מושגים מדעיים.
המאמר מומלץ מאוד מאוד! 200284
דה-קארט • בתשובה לדה-קארט יום ד', 25/2/2004, 0:43
מעלה המון תובנות בקשר לחלק מהשאלות שהועלו כאן, במיוחד הקשר של צ'רצ-טיורינג לגדל, ולמגבלות הפיסיקליות השונות (פלאנק ושות').
המאמר מומלץ קצת 202436
אלון עמית • בתשובה לדה-קארט יום ד', 3/3/2004, 9:00
אני מצטרף להמלצה לקרוא את המאמר - תמיד דבר טוב - אבל לעניות דעתי הוא לא כל-כך מעניין, לא מדויק לפרקים, וחוטא בכתיבה שיווקית מופרזת מאוד. אם מישהו רוצה אפשר לפצוח בדיון סוער על הבעיות במאמר והשאלה אם Hypercomputation זה מעניין.

(אגב, fair non-determinism לא מתחמק (כמובן) מהבעיות הקשורות באינסוף - קרא את הקטע עם הלמה של Koenig).
המאמר מומלץ קצת 202452
דה-קארט • בתשובה לאלון עמית יום ד', 3/3/2004, 10:18
כן, הבנתי את זה בקריאה היותר מלאה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות