האיש שחלם על מכונות: על חייו ומותו של אלן טיורינג, חלק ראשון

בתשובה לגדי אלכסנדרוביץ', 13/06/08 20:02

כמה הערות

481339

גדי אלכסנדרוביץ' • בתשובה לגדי אלכסנדרוביץ'

יום ו', 13/6/2008, 21:08

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

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

המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
RSS מאמרים \| כתבו למערכת \| אודות האתר \| טרם התעדכנת \| ארכיון \| חיפוש \| עזרה \| תנאי שימוש	© כל הזכויות שמורות