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