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

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

1 תחת ההנחות שציין אלון. וניתן להסיר אותן במאמץ קטן.
התיזה של צ'רץ'-טיורינג 199753
תוכל לתת כמה דוגמאות של הפונקציות הללו, או שרק הוכח הקיום שלהן אבל לא מצאו דוגמא? (אני חושב שאני זוכר במעורפל ששמעתי משהו על שימוש במשפט קנטור על קבוצת השפות הפורמליות או משהו בסגנון. צריך ללמוד את זה באמת)
התיזה של צ'רץ'-טיורינג 199769
המינוח המדוייק שצריך להשתמש בו הוא שפות בלתי כריעות (השתמשתי במונח פונקציות רק לצורך הבהרה). מצאו כמה כאלו, אבל הדוגמא היחידה שאני זוכר זו בעית העצירה‏1.
הקיום של הרבה שפות בלתי כריעות כאלו נובע בפשטות מכך שיש הרבה יותר שפות (שתיים בחזקת ALEF EFES) מאשר אלגוריתמים (ALEF EFES).
_________
1 בהינתן מכונת טורינג M וקלט מסויים עבורה X, החלט האם M תסיים את ריצתה על X בזמן סופי או לא (בשפת העם, תיכנס ללולאה אינסופית).
התיזה של צ'רץ'-טיורינג 199775
קצת מוזר שמכל הטקסט הזה, את שתי המלים הכי-עבריות החלטת לשעתק: ALEF זה אלף, EFES זה אפס.
נכון 199787
אני הייתי נזהר לגבי הניסוח הזה של תזת צ'רצ'-טורינג 200125
ראה, למשל:
אני הייתי נזהר לגבי הניסוח הזה של תזת צ'רצ'-טורינג 200160
תודה. הנושא של fair non-determinism נשמע מעניין מאוד. שאר המודלים האלטרנטיביים מסתמכים באופן "כבד" על איזשהוא משאב אינסופי, ואז זה לא מאוד מפתיע שיש להם יותר כח (אני מקווה שלא יסתבר שגם ה-fair non-determinism מסתמך על משאב אין סופי).

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

____
1 "הנחה" זו עוד דוגמא לכפל משמעות הנהדר שיש בעברית בכמה מושגים מדעיים.
המאמר מומלץ מאוד מאוד! 200284
מעלה המון תובנות בקשר לחלק מהשאלות שהועלו כאן, במיוחד הקשר של צ'רצ-טיורינג לגדל, ולמגבלות הפיסיקליות השונות (פלאנק ושות').
המאמר מומלץ קצת 202436
אני מצטרף להמלצה לקרוא את המאמר - תמיד דבר טוב - אבל לעניות דעתי הוא לא כל-כך מעניין, לא מדויק לפרקים, וחוטא בכתיבה שיווקית מופרזת מאוד. אם מישהו רוצה אפשר לפצוח בדיון סוער על הבעיות במאמר והשאלה אם Hypercomputation זה מעניין.

(אגב, fair non-determinism לא מתחמק (כמובן) מהבעיות הקשורות באינסוף - קרא את הקטע עם הלמה של Koenig).
המאמר מומלץ קצת 202452
כן, הבנתי את זה בקריאה היותר מלאה.

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

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