מה לא יכול המחשב לעשות

בתשובה לראובן, 14/12/06 11:08

בעית העצירה

424462

אורי גוראל-גורביץ' • בתשובה לראובן

יום ה', 14/12/2006, 11:23

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

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

המאמר המלא

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