בתשובה לעדי סתיו, 17/12/06 13:39
Reset 424907
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום א', 17/12/2006, 13:52
לא חסרות כאלו; יש המוני סוגים שונים ומשונים של מכונות טיורינג עם מגבלות עליהן. מגבלה שכבר ציינתי לא מעט בדיון היא מגבלה על הזיכרון; אם עבור מכונת טיורינג, הזיכרון המקסימלי שהיא משתמשת בו בריצה על קלט הוא פונקציה (ניתנת לחישוב) של גודל הקלט, אפשר לפתור את בעיית העצירה עבור המכונה הזו.
שואל ועונה 424914
קהלת • בתשובה לגדי אלכסנדרוביץ' יום א', 17/12/2006, 14:42
הבעיה שהצגתי קודם (חיפוש פתרון למשוואה) משתמשת בכמות סופית של זיכרון (אין צורך לזכור פתרונות קודמים, פחות יעיל אבל עדין עובד), איך מיישבים את הסתירה ?
ראוי לציין שהמכונה שלי משתמשת ביכולת להגריל מספרים אקראיים, תכונה שלא באמת קיימת במ"ט (בעצם אפשר לראות בזה הוכחה לכך שמ"ט לעולם לא תוכל להגריל מספרים אקראיים)
שואל ועונה 424918
קהלת • בתשובה לקהלת יום א', 17/12/2006, 14:52
בעצם טעיתי. הגבלה על גודל הזיכרון מגבילה את גודל המספר המנוחש.
שואל ועונה 424934
האייל האלמוני • בתשובה לקהלת יום א', 17/12/2006, 15:40
...ובעיקר את אורכו.
שואל ועונה 424958
גדי אלכסנדרוביץ' • בתשובה לקהלת יום א', 17/12/2006, 19:41
כבר ענית היטב לעצמך. רק הערה קטנה: לא קשה להוכיח שגם מכונת טיורינג *אי דטרמיניסטית* (מושג שעליו ארחיב, אם בכלל, במאמר המשך למאמר ההמשך) לא חזקה יותר ממכונת טיורינג רגילה - ואי דטרמיניזם, מבחינה רעיונית, הוא יותר חזק מאקראיות "סתם" (אם כי זה לא כל כך פשוט - במכונות אקראיות מרשים לפעמים למכונה לטעות - ובפרט, יש מכונה אקראית שפותרת את בעיית העצירה בהסתברות 1/2).
שואל ועונה 424959
קהלת • בתשובה לגדי אלכסנדרוביץ' יום א', 17/12/2006, 19:49
מחכה בקוצר רוח.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות